寶音

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

寶音

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

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

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

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

1 預(yù)備知識

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

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

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

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

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

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

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

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

(ii)圖G是伴隨唯一的當(dāng)且僅當(dāng)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)提出公項(xiàng)，逐項(xiàng)遞推和式(ii)得

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

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

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

用數(shù)學(xué)歸納法來可以證明公式(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］寶音.一類圖簇的伴隨多項(xiàng)式的恒等式及其因式分解［J］.陰山學(xué)刊，2007，21(3):9－10.

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

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

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

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

［7］曹輝.三類組合圖的伴隨多項(xiàng)式的因式分解及其色性分析［J］.西南師范大學(xué)學(xué)報(bào):自然科學(xué)版，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

青海省自然科學(xué)基金資助項(xiàng)目(2011－Z－911)

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