寶音

（青海民族大學(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的補(bǔ)圖，G1∪G2表示圖G1與G2和的點(diǎn)不重并.NG表示N個(gè)圖G的點(diǎn)不重并.未加說明的記號(hào)和術(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.本文將圖G(Pn

r)推廣到，并證明了圖簇的伴隨多項(xiàng)式的伴隨等價(jià)，據(jù)此討論了)類圖簇的伴隨多項(xiàng)式的因式分解問題，給出并證明了它們的補(bǔ)圖的色等價(jià)圖的結(jié)構(gòu)特征.

1 預(yù)備知識(shí)

設(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的任何三角形，則

h(G,x)=h(G-uv,x)+xh(G-{u,v},x)

引理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)的路和圈，則有

引理4[5]設(shè)G是任意圖，則h(G∪k1,x)=h(G,x)hn(k1,x) =xnh(G,x).

引理5[6](i)圖G與H是伴隨等價(jià)的當(dāng)且僅當(dāng)G與H式色等價(jià)的；

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

引理7[7]設(shè)G是p階連通的對(duì)稱圖，p≥2,p≥i≥1；vi∈v(G);r≥1;m≥2

引理8[7]設(shè)G是p階連通的對(duì)稱圖，p≥2,p≥i≥1；vivj∈E(G);r≥1;

引理9[8]設(shè)m,n∈N,m≥1,n≥1，則有

引理10[8]設(shè)t≥1的任意自然數(shù)而q≥3是給定的正奇數(shù)，并且m,n∈N,m≥1,n≥1，則有

定義2設(shè)G是p階連通圖，把Sm+1中的第m個(gè)頂點(diǎn)分別與圖(其中記號(hào)及其對(duì)應(yīng)的圖簇均見文[2])的每個(gè)點(diǎn)重迭后得到的圖記為；把圖中的每一個(gè)Pn+1的每一個(gè)點(diǎn)與圖Sm+1中每一個(gè)m個(gè)頂點(diǎn)分別重迭后得到的圖記為

圖1 圖

圖2 圖

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

對(duì)公式(6)提出公項(xiàng),逐項(xiàng)遞推和式(ii)得

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

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

證明（i）當(dāng)r=1時(shí)，在圖h(PSmP(1,n+1))中均取uv=v00v11，則由引理1和引理2可得到式（7）

(ii)當(dāng)r=2時(shí)，在圖h(PSmP(2,n+1))中均取uv=v00v11，則由引理1和引理2和(i)得到

(iii)在圖h(PSmP(r,n+1))中均取uv=v00v11，則由引理1和引理2得到

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

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

2 因式分解與色性分析

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

證明由引理2，引理4，引理11(iii)和引理12(iii)，即得結(jié)論

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

推理1設(shè)G是不含三角形的任意p階連通圖，則有

定理2設(shè)G是p階連通的對(duì)稱圖，p≥2,p≥i≥1；vi∈v(G);r=m≥2

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

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

定理3設(shè)G是p階連通的對(duì)稱圖，p≥2,p≥i≥1；vivj∈E(G);r≥1;

證明由引理2，引理4，引理8和定理2，即得結(jié)論.

定理4設(shè)m,n,r∈N,m≥2,n≥2,r≥2，則有

證明由引理2，引理4，引理9和定理1，即得結(jié)論.

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

定理5設(shè)G是不含三角形的任意p階連通圖，t≥1的任意自然數(shù)而q≥3是給定的正奇數(shù)，r≥i≥3;r≥1;n≥2則有

證明由引理2，引理4，引理10和定理1，即得結(jié)論.

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

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

定理7設(shè)G是p階連通的對(duì)稱圖，p≥2,p≥i≥1；vi∈v(G);;r=m≥2

定理8設(shè)G是p階連通的對(duì)稱圖，p≥2,p≥i≥1；vivj∈E(G);;r≥1

定理9設(shè)m,n,r∈N,m≥2,n≥2,r≥2，則圖簇

定理10設(shè)G是不含三角形的任意p階連通圖，t≥1的任意自然數(shù)而q≥3是給定的正奇數(shù)，r≥i≥3;r≥1;n≥2則圖簇二者的補(bǔ)圖是色等價(jià)的.

〔1〕Harary.Graph,theory[M].Addison Wesley,1969.

〔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é)研究與評(píng)論, 1994，14（3）：469-472.

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

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

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

O157.5

A

1673-260X（2013）07-0001-04

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