索南仁欠,李生剛

(1.陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,陜西西安 710062;2.青海師范大學(xué)數(shù)學(xué)系,青海西寧 810008)

ΦS-型圖簇的伴隨分解及其色性分析

索南仁欠1,2,李生剛1

(1.陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院,陜西西安 710062;2.青海師范大學(xué)數(shù)學(xué)系,青海西寧 810008)

運(yùn)用圖的伴隨多項(xiàng)式的性質(zhì),討論了圖簇ΦS((kn+1)σ,nσ)∪2kSσ的伴隨多項(xiàng)式的因式分解定理,進(jìn)而證明了它們的補(bǔ)圖的色等價(jià)性.

色多項(xiàng)式;伴隨多項(xiàng)式;因式分解;色等價(jià)性

1 預(yù)備知識(shí)及準(zhǔn)備工作

圖1

圖2

圖3 ΨS(kσ,nσ)

圖4 ΦS((kn+1)σ,nσ)

2 因式分解定理

3 色等價(jià)性分析

參考文獻(xiàn)

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

[2]周登杰.路和圈多重聯(lián)圖的鄰點(diǎn)可區(qū)別E-全染色[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(6):909-914.

[3]王艷芳.4度Cayley圖的Hamilton圈分解的新方法與理論證明[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2010,26(3):380-386.

[4]鄭國彪.D-完全一致混合超圖不可著色的一個(gè)充要條件[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2011,27(3):308-312.

[5]劉儒英.求圖的色多項(xiàng)式的一種新方法及其應(yīng)用[J].科學(xué)通報(bào),1987,32:1508-1509.

[6]Liu R Y.Adjoint polynomials and chromatically unique graphs[J].Discrete Mathematics,1997,172:85-92.

[7]張秉儒.幾類圖簇的伴隨多項(xiàng)式的因式分解及其色性分析[J].數(shù)學(xué)學(xué)報(bào),2002,45(3):529-534.

[8]馬海成.構(gòu)造色等價(jià)圖的幾種新方法[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào),2004,19(2):135-140.

[9]Read R C.An introduction to chromatic polynomials[J].Combin.Theory,1968,4:52-71.

[10]Farrell E J.An introduction to matching polynomials[J].Combin.Theory(B),1979,27:75-86.

[11]Biggs N.Algebraic Graph Theory[M].Cambridge:Cambridge University Press,1974.

[12]劉儒英.兩類圖的色多項(xiàng)式的求法[J].科學(xué)通報(bào),1987,32:1147-1148.

[13]張秉儒.圖的伴隨多項(xiàng)式的因式分解定理及其應(yīng)用[J].數(shù)學(xué)學(xué)報(bào),2005,48(1):125-132.

[14]劉儒英.圖的補(bǔ)圖的色唯一性[J].數(shù)學(xué)研究與評(píng)論,1994,14:469-472.

[15]Zhang B R.The factorization of adjoint polynomials of class graphs and chromatically equivalence analysis[J].數(shù)學(xué)季刊,2008,23(3):376-383.

[16]侯海存,張秉儒.一類新的圖簇的伴隨分解定理及其補(bǔ)圖的色等價(jià)性[J].西南師范大學(xué)學(xué)報(bào),2010,35(4):69-73.

The factorization of adjoin polynomials of graphs of ΦS-shape and chromatic non-uniqueness analysis

Suonan Renqian1,2,Li Shenggang1

(1.College of Mathematics and Information science,Shanxi normal university,Xi′an710062,China;
2.Department of Mathematics,Qinghai Normal University,Xining810008,China)

By applying the properties of adjoint polynomials,We prove that factorization theorem of adjoint polynomials of a kind of graphs ΦS((kn+1)σ,nσ)∪2kSσ,Furthermore,we obtain chromatically equivalence of its complements.

chromatic polynomial,adjoint polynomials,factorization,chromatically equivalent graph, structure characteristics

O157.5

A

1008-5513(2013)06-0551-08

10.3969/j.issn.1008-5513.2013.06.001

2013-10-08.

國家自然科學(xué)基金(11061026,11071151).

索南仁欠(1969-),博士生,教授,研究方向：計(jì)算數(shù)學(xué),代數(shù)組合論.

2010 MSC:05C78