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

寶音

（青海民族大學蒙學系，青海西寧810007）

寶音

（青海民族大學蒙學系，青海西寧810007）

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

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

我們僅考慮簡單圖，用V（G）和E（G）分別表示G的頂點集和邊集表示圖G的補圖，G1∪G2表示圖G1與G2和的點不重并.NG表示N個圖G的點不重并.未加說明的記號和術語均來自文[1].設P（G，Λ）是圖G的色多項式，稱圖G與H是色等價的，若P（G，λ）=P（H，λ）；稱圖G是色唯一的，若從P（H，λ）=P（G，λ）推出圖H與G同構，記為H≌G.本文將圖G(Pn

r)推廣到，并證明了圖簇的伴隨多項式的伴隨等價，據此討論了)類圖簇的伴隨多項式的因式分解問題，給出并證明了它們的補圖的色等價圖的結構特征.

1 預備知識

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

n=|v(G)|？,其中(λ)k=λ(λ-1)(λ-2)…(λ-k+1).定義1[3]設G是n階圖，則多項式

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

引理1[3]設UV∈E(G)且UV不屬于G的任何三角形，則

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

引理2[3]設圖G有k個分支G1,G2,…,GK,則h(G,x)=h (G1,x)h(G2,x)…h(GK,x).

引理3[4]設Pn和Cn分別表示具有n個頂點的路和圈，則有

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

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

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

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

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

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

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

定義2設G是p階連通圖，把Sm+1中的第m個頂點分別與圖(其中記號及其對應的圖簇均見文[2])的每個點重迭后得到的圖記為；把圖中的每一個Pn+1的每一個點與圖Sm+1中每一個m個頂點分別重迭后得到的圖記為

圖1 圖

圖2 圖

引理11設r≥i≥3;r≥1;n≥2則

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

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

引理12設r≥i≥3;r≥1;n≥2則

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

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

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

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

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

2 因式分解與色性分析

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

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

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

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

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

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

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

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

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

定理4設m,n,r∈N,m≥2,n≥2,r≥2，則有

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

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

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

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

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

類似地，根據引理4，引理5和定理2，定理3，可證如下的結論

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

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

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

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

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

〔3〕劉儒英.求圖的色多項式的一種新方法及應用[J].科學通報,1987，32,77.

〔4〕劉儒英.關于兩類圖的色多項式[J].科學通報,1987（32）：236.

〔5〕劉儒英.Pq-1的補圖的色唯一性[J].數學研究與評論, 1994，14（3）：469-472.

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

〔7〕張秉儒.圖的伴隨多項式的因式分解定理及應用[J].數學學報,2005，48（1）：125-132.

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

O157.5

A

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

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