火博豐,劉儒英

(青海師范大學(xué)數(shù)學(xué)系,青海西寧 810008)

Dn補(bǔ)圖的色唯一性

火博豐,劉儒英

(青海師范大學(xué)數(shù)學(xué)系,青海西寧 810008)

利用伴隨多項(xiàng)式來(lái)討論圖的著色唯一性是近二十年來(lái)出現(xiàn)的新方法.用Pn表示有n個(gè)頂點(diǎn)的路.Dn表示把K3的一個(gè)頂點(diǎn)與Pn?2的一個(gè)一度頂點(diǎn)重迭后得到的圖.該文推廣了相關(guān)文獻(xiàn)的結(jié)論,得到n色唯一當(dāng)且僅當(dāng)n/=4且n/=8.徹底解決了這類(lèi)圖的色性.

色多項(xiàng)式；色唯一性；伴隨多項(xiàng)式；伴隨唯一性

1 定義和基本引理

2 伴隨多項(xiàng)式相關(guān)性質(zhì)及重要引理

3 Dn補(bǔ)圖的色唯一性

[1]邦迪J A,默蒂U S.圖論及其應(yīng)用[M].北京:科學(xué)出版社,1984.

[2]Liu Ruying.Ad joint polynomialsand chromatically unique graphs[J].DiscreteMathematics,1997,172:85-92.

[3]Liu Ruying,Zhao Lian chang.A new m ethod for p roving chrom atic uniqueness of graphs[J].Discrete Mathematics,1997,171:169-177.

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

[5]杜清晏.圖的參數(shù)π(G)及其圖的分類(lèi)[J].內(nèi)蒙古大學(xué)學(xué)報(bào),1995,26(3):258-262.

[6]火博豐.圖的三個(gè)參數(shù)A(G),R(G)及D2(G)的關(guān)系[J].青海師范大學(xué)學(xué)報(bào),1998,2:1-6.

[7]劉儒英.圖的伴隨多項(xiàng)式[J].青海師范大學(xué)學(xué)報(bào),1990,3:1-9.

[8]Du Qingyian.Chrom aticity of com p lem ents of paths and cycles[J].D iscrete Mathem atics,1996,162:109-125.

[9]火博豐,劉儒英.關(guān)于Dn補(bǔ)圖色性證明的一個(gè)重要引理[J].青海師專(zhuān)學(xué)報(bào),2005,3:12-15.

[10]Cvetkovi D,Doob M,Sachs H.Spectra of graphs[M].New York:Academ ic Press,1980:72-79.

[11]趙海興,火博豐,劉儒英.路的補(bǔ)圖的色唯一性[J].數(shù)學(xué)研究,2000,4:345-353.

[12]Du Qingyian.Onσ-equivalence andχ-equivalence of graphs[J].Journal of G raph Theory.1996,21(2):211-217.

[13]王守中,劉儒英.圈和Dn圖的補(bǔ)圖的色唯一性[J].數(shù)學(xué)研究與評(píng)論,1998,2:296.

[14]王力工,劉儒英.一類(lèi)樹(shù)并補(bǔ)圖的色唯一性[J].純粹數(shù)學(xué)與應(yīng)用數(shù)學(xué),2001,17(2):126.

Chrom aticity of the complements of Dn

HUO Bo-feng,LIU Ru-ying

(Department of Mathematics,Qinghai Normal University,Xining 810008,China)

The paper show the chrom aticity of some dense graphs by em p loying the ad joint polynomial.Let Pndenote the Path of order n,Dnthe graph that identify a vertex of K3with an end-vertex of Pn?2.we generalize the conclusion and obtain that the com p lements of Dnare chromatic uniqueness if and only if n/=4 and n/=8,which com p letely solve this p roblem.

chrom atical polynomial,chrom aticity,ad joint polynomial,ad joint uniqueness

O157.5

A

1008-5513(2009)02-0268-08

2007-11-05.

國(guó)家自然科學(xué)基金(10761008),教育部自然科學(xué)重點(diǎn)研究項(xiàng)目(205170).

火博豐(1967-),副教授,研究方向：圖論.

2000M SC:05C15