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

王青宁,李银奎

(青海民族大学数学与统计学院,青海 西宁 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,称图G是伴随唯一的.显然G～H当且仅当Hc～Gc.G色唯一当且仅当Gc是伴随唯一的.因此,研究图的伴随等价、伴随唯一是为了研究图的色等价和色唯一.关于此方面的研究人们已经给出了许多好的结果[34],但尚有一些问题还未完全解决,比如如何确定一个图的伴随等价图的个数问题等等.本文将研究一些路的并图的伴随等价图的计数问题,进而给出这些图的补图的色等价图的个数计算公式.首先介绍一些有用的引理.

2 有关引理

3 主要结果和证明

对整数 m+1(≥3)按其所含的最大奇因数进行分类.若 m+1的最大奇因数是 1,即m+1=2n−1(3+1)=2n+1时,称m属于3-系,且是第n-级的.如31是3系第4级的数(因31+1=24+1).若m+1的最大奇因数2k+1(k≥1),即m+1=2n−1(2k+1)时,称m属于2k-系,且是第n-级的.如55是6-系第4级的数(因55+1=24−1(6+1)).于是每个整数m(≥2)均属于且仅属于一个系.设A是一些大于等于2的整数组成的可重集,则A可以分解为属于不同系的整数构成的可重集的并集.为了叙述方便,约定:可重集

[1]Bondy J A,Murty U S R.Graph Theory with Applications[M].Amsterdam:North-Holland,1976.

[2]Liu Ruying.Adjoint polynomials chromatically unigue,gragh[J].Discrete Math.,1997(172):85-92.

[3]王力工,刘儒英.一类树并补图的色惟一[J].纯粹数学与应用数学,2001,17(2):25-30.

[4]张海良.几类图的匹配多项式之间的关系和一类图的匹配等价图[J].纯粹数学与应用数学,2007,23(2):37-42.

[5]Ma Haicheng,Ren Haizhen.The chromatic classes of the complements of graphs with the minimum real roots of the adioint polynomials greater than−4[J].Discrete Math.,2004(259):277-294.

[6]Zhao H X,Li X L,Zhang S G,et al.On the minimum real roots of the-polynomials and chromatic uniqueness of graphs[J].Discrete Math.,2004(259):277-294.

[7]马海成.路并的匹配等价图数[J].数学研究,2006(2):218-222.

[8]王青宁.路并伴随等价图计数的一种新方法[J].西安文理学院学报,2008(2):45-48.

The formular for counting the number of adjoint equivalence graphs of 2-series integers reset except number 2

Wang Qingning,Li Yinkui
(Department of Mathematics,Qinghai Nationalities College,Xining 810000,China)

In order to study some combinatorial properties of a graph,we discuss the counting problem of the number of the adjoint equivalence graphs.By counting the number of repeated sets which composed by 2-series integers.In this paper,we give a combination formula for computing the number of the hromatic equivalence graphs of its complement graph.Here we provide a new method for counting the number of the adjoint equivalence graphs,and this is more concise than the traditional methods.

ajoint-polynomial,chromatic-polynomial,adjoint equivalence,chromatic

O157.5

A

1008-5513(2012)05-0585-05

2013-03-10.

教育部春晖计划(Z2010071).

王青宁(1968-),副教授,研究方向:图论与组合.

2010 MSC:05C78