不含整數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