王青寧,李銀奎

(青海民族大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,青海 西寧 810007)

不含整數(shù)2的2-系整數(shù)組成的可重集的計數(shù)公式

王青寧,李銀奎

(青海民族大學(xué)數(shù)學(xué)與統(tǒng)計學(xué)院,青海 西寧 810007)

為了更好地研究圖的組合性質(zhì),就特殊圖類的伴隨等價圖的計數(shù)問題做了討論.通過討論由2-系整數(shù)組成且不含整數(shù)2的可重集的色等價圖的計數(shù)問題得到伴隨等價圖的計數(shù)方法.給出了伴隨等價圖及其補圖的色等價圖的個數(shù)的計算公式.本文提供了一種圖的伴隨等價計數(shù)的新方法,此方法比傳統(tǒng)方法更為簡潔.

伴隨多項式;色多項式;伴隨等價;色等價

1 引言

本文僅考慮有限無向簡單圖.K1表示一個孤立點,Pn(n≥2)和Cn(n≥3)分別表示有n個頂點的路和圈.設(shè)G和H是兩個圖,以G∪H表示圖G和H的不交并,kG表示k個圖G的不交并.以[G]表示圖G的所有伴隨等價圖的集合,β(G)表示圖G的伴隨多項式h(G,x)的最小實根,用δ(G)表示圖G的所有不同構(gòu)的伴隨等價圖的個數(shù),即δ(G)=|[G]|.顯然δ(G)=1當且僅當圖G伴隨唯一.本文未加說明的術(shù)語和記號參見文獻[1].

設(shè)G是有n個點的簡單圖,若其補圖的色多項式為

叫 G的伴隨多項式,通常簡記為 h(G).每個分支都是完全圖 G的生成子圖叫 G的理想子圖,ai的組合意義是G的具有i個分支的理想子圖的個數(shù).對伴隨多項式的研究參見文獻[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是伴隨唯一的.因此,研究圖的伴隨等價、伴隨唯一是為了研究圖的色等價和色唯一.關(guān)于此方面的研究人們已經(jīng)給出了許多好的結(jié)果[34],但尚有一些問題還未完全解決,比如如何確定一個圖的伴隨等價圖的個數(shù)問題等等.本文將研究一些路的并圖的伴隨等價圖的計數(shù)問題,進而給出這些圖的補圖的色等價圖的個數(shù)計算公式.首先介紹一些有用的引理.

2 有關(guān)引理

3 主要結(jié)果和證明

對整數(shù) m+1(≥3)按其所含的最大奇因數(shù)進行分類.若 m+1的最大奇因數(shù)是 1,即m+1=2n?1(3+1)=2n+1時,稱m屬于3-系,且是第n-級的.如31是3系第4級的數(shù)(因31+1=24+1).若m+1的最大奇因數(shù)2k+1(k≥1),即m+1=2n?1(2k+1)時,稱m屬于2k-系,且是第n-級的.如55是6-系第4級的數(shù)(因55+1=24?1(6+1)).于是每個整數(shù)m(≥2)均屬于且僅屬于一個系.設(shè)A是一些大于等于2的整數(shù)組成的可重集,則A可以分解為屬于不同系的整數(shù)構(gòu)成的可重集的并集.為了敘述方便,約定:可重集

[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].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2001,17(2):25-30.

[4]張海良.幾類圖的匹配多項式之間的關(guān)系和一類圖的匹配等價圖[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),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]馬海成.路并的匹配等價圖數(shù)[J].數(shù)學(xué)研究,2006(2):218-222.

[8]王青寧.路并伴隨等價圖計數(shù)的一種新方法[J].西安文理學(xué)院學(xué)報,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