圖簇的伴隨多項式的因式分解及其補圖的色等價性*

寶音

(青海民族大學蒙學系，青海西寧810007)

寶音

(青海民族大學蒙學系，青海西寧810007)

本文利用圖的伴隨多項式的性質(zhì)及其伴隨分解的圖論方法，討論了型圖的伴隨多項式的因式分解，進而證明了在不同條件下這類圖的補圖的色等價性.

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

我們僅考慮簡單圖，用V(G)和E(G)分別表示G的頂點集和邊集，G表示圖G的補圖，G1∪G2表示圖G1與G2和的點不重并。NG表示N個圖G的點不重并。未加說明的記號和術(shù)語均來自文［1］。設(shè)P(G，λ)是圖G的色多項式，稱圖G與H是色等價的，若P(G，λ)=P(H，λ);稱圖G是色唯一的，若從P(H，λ)=P(G，λ)推出圖H與G同構(gòu)，記為H≌G。

1 預(yù)備知識

設(shè)G是n階圖，若圖G的生成子圖M的每個分支都是完全圖，則稱M是G的理想子圖，用N(G，K)表示圖G的具有k個分支的理想子圖的個數(shù)，則圖的色多項式可以表示為［3］，設(shè)G是n階圖，

n=|v(G)|，其中(λ)k=λ(λ－1)(λ－2)…(λ－k+1)．

定義1［3］:設(shè)G是n階圖，則多項式

稱為圖G的伴隨多項式并且簡記為h(G)。

引理1［3］:設(shè)uv∈E(G)且uv不屬于G的任何三角形，則

引理2［3］:設(shè)圖G有k個分支G1，G2，…GK，則h(G，x)=h(G1，x)h(G2，x)…h(huán)(GK，x)。

引理3［4］:設(shè)Pn和Cn分別表示具有n個頂點的路和圈，則有

引理5［6］:(i)圖G與H是伴隨等價的當且僅當與式色等價的;

(ii)圖G是伴隨唯一的當且僅當G 色唯一的。

引理6［6］:設(shè)Sn+1是n+1階的星圖，則h(Sn+1，x)=xh(Sn，x)+xn

引理7［7］:設(shè)r，m?N;r≥2;m≥1則

圖1:圖

圖2:圖

引理8:設(shè)r≥i≥3;r≥1;n≥2則

對公式(6)提出公項，逐項遞推和式(ii)得

用數(shù)學歸納法來可以證明公式(5)對一切自然數(shù)都成立。

引理9:設(shè)r≥i≥3;r≥1;n≥2則

對公式(10)提出公項，逐項遞推和式(ii)得

用數(shù)學歸納法來可以證明公式(9)對一切自然數(shù)都成立。

2 因式分解與色性分析

定理1:設(shè)G是不含三角形的任意p階連通圖，r≥i≥3;r≥1;n≥2則有

證明:由引理2，引理4，引理8(iii)和引理9(iii)，即得結(jié)論

因此，即(i)的結(jié)論成立。由(i)式及引理2和引理4容易推知(ii)式也成立。

推理1:設(shè)G是不含三角形的任意p階連通圖，r≥i≥3;r≥1;n≥2則有

定理2:設(shè)G是不含三角形的任意p階連通圖，r，n，m?N，r≥1;n≥2，m≥1則有

證明:由引理4，引理7和定理1，即得結(jié)論

因此，即(i)的結(jié)論成立。由(i)式及引理2和引理4容易推知(ii)式也成立。

定理3:設(shè)G是不含三角形的任意p階連通圖，r，n，m?N，r≥1;n≥2，m≥1則有

證明:由引理4，引理7和定理1，即得結(jié)論

因此，即(i)的結(jié)論成立。由(i)式及引理2和引理4容易推知(ii)式也成立。

類似地，根據(jù)引理4，引理5和定理2，定理3，可證如下的結(jié)論

［1］Harary.Graph Theory［M］.Reading MA:Addison Wesley，1969.

［2］寶音.一類圖簇的伴隨多項式的恒等式及其因式分解［J］.陰山學刊，2007，21(3):9－10.

［3］劉儒英:求圖的色多項式的一種新方法及應(yīng)用［J］.科學通報，1987，32，77.

［4］劉儒英:關(guān)于兩類圖的色多項式［J］.科學通報，1987，32，236.

［5］劉儒英:Pq－1的補圖的色唯一性［J］.數(shù)學研究與評論，1994，14(3):469－472.

［6］寶音，張秉儒.SP(i)類圖簇的伴隨多項式的因式分解及其色性分析［J］.西南師范大學學報:自然科學版，2004，29(4):573－577.

［7］曹輝.三類組合圖的伴隨多項式的因式分解及其色性分析［J］.西南師范大學學報:自然科學版，2007，32(5): 18－21.

The Adjoint FactorizationsofGraphs of－shape and Chromatically Equivalence of their Complement

BAO Yin
(Dept.of Mongol.，Qinghai National University;Xining 810007)

Chromatic polynomial;Adjoint polynomial;Factorization;Chromatically equivalence

O157.5

A

1004－1869(2014)01－0005－04

2013－11－04

青海省自然科學基金資助項目(2011－Z－911)

寶音(1962－)，男，內(nèi)蒙古赤峰人，教授，研究方向:圖論和組合數(shù)學。