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

索南仁欠,李生剛

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

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

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

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

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

色多項式;伴隨多項式;因式分解;色等價性

1 預備知識及準備工作

圖1

圖2

圖3 ΨS(kσ,nσ)

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

2 因式分解定理

3 色等價性分析

參考文獻

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

[2]周登杰.路和圈多重聯圖的鄰點可區別E-全染色[J].純粹數學與應用數學,2010,26(6):909-914.

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

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

[5]劉儒英.求圖的色多項式的一種新方法及其應用[J].科學通報,1987,32:1508-1509.

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

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

[8]馬海成.構造色等價圖的幾種新方法[J].高校應用數學學報,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]劉儒英.兩類圖的色多項式的求法[J].科學通報,1987,32:1147-1148.

[13]張秉儒.圖的伴隨多項式的因式分解定理及其應用[J].數學學報,2005,48(1):125-132.

[14]劉儒英.圖的補圖的色唯一性[J].數學研究與評論,1994,14:469-472.

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

[16]侯海存,張秉儒.一類新的圖簇的伴隨分解定理及其補圖的色等價性[J].西南師范大學學報,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.

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

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

2010 MSC:05C78