王青宁,李银奎

(青海民族大学数学与统计学院,青海 西宁 810007)

不含整数2的2-系整数组成的可重集的计数公式

王青宁,李银奎

(青海民族大学数学与统计学院,青海 西宁 810007)

为了更好地研究图的组合性质,就特殊图类的伴随等价图的计数问题做了讨论.通过讨论由2-系整数组成且不含整数2的可重集的色等价图的计数问题得到伴随等价图的计数方法.给出了伴随等价图及其补图的色等价图的个数的计算公式.本文提供了一种图的伴随等价计数的新方法,此方法比传统方法更为简洁.

伴随多项式;色多项式;伴随等价;色等价

1 引言

本文仅考虑有限无向简单图.K1表示一个孤立点,Pn(n≥2)和Cn(n≥3)分别表示有n个顶点的路和圈.设G和H是两个图,以G∪H表示图G和H的不交并,kG表示k个图G的不交并.以[G]表示图G的所有伴随等价图的集合,β(G)表示图G的伴随多项式h(G,x)的最小实根,用δ(G)表示图G的所有不同构的伴随等价图的个数,即δ(G)=|[G]|.显然δ(G)=1当且仅当图G伴随唯一.本文未加说明的术语和记号参见文献[1].

设G是有n个点的简单图,若其补图的色多项式为

叫 G的伴随多项式,通常简记为 h(G).每个分支都是完全图 G的生成子图叫 G的理想子图,ai的组合意义是G的具有i个分支的理想子图的个数.对伴随多项式的研究参见文献[2].若两个图G和H有P(G,λ)=P(H,λ),则称图G和H是色等价的,记为G～H.若与图G色等价的任何图H,都有HG,则称G是色唯一的.类似地,若两个图G和H有h(G,x)=h(H,x),称图G和H是伴随等价的,简记为G～H.若与图G伴随等价的任何图H,都有H～=G,称图……