Y（2，2，λ）形圖的伴隨多項式的分解及其補圖的色等價性

王云，蘆殿軍，張秉儒

（1.青海大學，青海 西寧810006；2.青海師范大學數學系，青海 西寧810008）

Y（2，2，λ）形圖的伴隨多項式的分解及其補圖的色等價性

王云1，蘆殿軍2，張秉儒2

（1.青海大學，青海 西寧810006；2.青海師范大學數學系，青海 西寧810008）

構造了兩類圖簇Y（2，2，λ）∪K1（m為奇數）和Y（2，2，λ）∪EGδ（m為偶數）.運用圖的伴隨多項式，討論了這兩類圖簇的伴隨多項式的因式分解式，（m=2k-1q-1，λk=（2kq-1）+2k-1qδ），研究了圖簇Y（2，2，λk）∪（k-1）K1和Y（2，2，λk）的伴隨多項式的因式分解式，進而證明了這些圖的補圖的色等價性.

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

1 預備知識

對于簡單圖來說，用V（G）表示圖G的頂點集.E（G）表示圖G的邊集.是圖G的補圖.G∪H和nG分別表示圖G和H的點不重并，n個圖G的點不重并，未加說明的記號和術語參考文獻［1-2］.設p（G，λ）為圖G的色多項式，稱圖G與H色等價，若p（G，λ）=p（H，λ）.稱圖G是色唯一圖，若從p（H，λ）=p（G，λ）得到圖H與G同構，記為G≌H.文獻［3-4］首先提出色等價圖和色唯一圖的概念.1987年文獻［5］提出了圖G的伴隨多項式h（G，x）和伴隨唯一性的概念，并在色唯一圖的研究中獲得一系列新成果［6-8］.目前色等價圖的結構規律尚待解決.本文中，由自然數m的奇偶性及已有的圖，構造了幾類

新的圖簇，且運用圖的伴隨多項式的性質，主要討論了

圖簇的伴隨多項式及其因式分解式，當m=2kq-1，λn=（2nq-1）+2n-1qr時，討論了圖簇Y（2，2，λk）∪（k-1）K1和Y（2，2，λk）的伴隨多項式的因式分解式，并且證明了上述圖簇的補圖的色等價性，確定了它們的補圖的色等價圖的構成規律.

2 圖的伴隨多項式的概念

設G是p階圖，若圖G的生成子圖G0的所有分支是完全圖，則稱G0為圖G的理想子圖.用bi（G）表示圖G的具有p-i個分支的理想子圖的個數（0≤i≤p-1），由文獻［4］的定理15可知

其中p=|V（G）|，（λ）k=λ（λ-1）（λ-2）···（λ-k+1）.

定義2.1［5］設G是p階圖，則圖G的多項式

稱為簡單圖G的伴隨多項式，h（G，x）可以簡記為h（G）.圖G的每個分支或是K1或是K2的生成子圖稱為圖G的一個匹配，圖G的一個K-匹配就是含有k條邊的匹配，由G的理想子圖的個數bi（G）的定義即得如下的.

引理2.1［5］若G是無三角形K3的圖，則bi（G）等于圖G的匹配數目.

定義2.2稱圖G與H是伴隨等價的，若h（G，x）=h（H，x），稱圖G是伴隨唯一的，若從h（G，x）=h（H，x）推出G與H同構，記為H≌G.

引理2.2［6］圖G與H是伴隨等價的當且僅當和是色等價的；圖G是伴隨唯一的當且僅當是色唯一的.

下面給出常用到圖的伴隨多項式h（G，x）的基本性質.

引理2.3［7］設uv∈E（G）且uv不屬于圖G的任何三角形，則有

引理2.4［7］設圖G具有k個分支G1，G2，···，Gk，則有

設G是任意的連通圖，其伴隨多項式為h（G，x），以下簡記為h（G）.根據引理2.4，易得下面引理成立.

引理2.5設G和H是任意的兩個圖，K1是一個孤立點，n≥2是任意的自然數，則有

引理2.6［10］設n≥2是自然數，Sn表示具有n個頂點的星圖，則有

3 幾類新圖的伴隨多項式

設G是任意的p階圖，nG表示n個圖G的不相交并，設Pn和Cn是具有n個頂點的路和圈，Sn是n個頂點的星圖，表示把星Sr+1的r個1度點分別與rG的每個分支的第i個頂點vi（1≤i≤p）重迭，并把另一個G的第i個頂點與Sr+1的r度點重迭后得到的圖（如圖3.1所示），其中δ=（r+1）p，r∈N，r≥2，di=d（vi）；設

圖3.1 EδG圖

圖3.2 圖

圖3.3 ΨK（2，m+2-1（m+1）δ）圖

圖3.4 圖

圖3.5 Y（2，m+2-1（m+1）δ）圖

圖3.6 ΨT（2δ，2，m+2-1mδ），m=2t圖

圖3.7 Y（2，2，（2m+1）+（m+1）δ）圖

引理3.1設m（≥3）是奇數，r是任意自然數，r≥1，δ=（r+1）p，p=|V（G）|，則有

引理3.3設m（≥4）為偶數，r是自然數，r≥1，δ=（r+1）p，p=|V（G）|，則有

證明 參考圖3.3，m是偶數，則m+1是奇數，故d（vm）=2，d（vm+1）=r+di+1，這里di=d（vi），vi∈V（G），在圖Ψk（2，m+2-1（m+1）δ）中取邊e=vmvm+1，則由引理2.3和引理2.4，立即推知（9）式成立.

引理3.4設m（≥3）為奇數，r是自然數，r≥1，δ=（r+1）p，p=|V（G）|，則有

證明 當m為奇數時，此時m+1與m-1均為偶數，d（u1）=1，d（v1）=di+r+1，這里di=d（vi），vi∈V（G），如圖3.4所示，在圖Y（1，2，m+2-1（m+1）δ）中取e=u1v1，由引理2.3和引理2.4，即得

上式右端提取公因子x，即得（10）式.

如圖3.5所示，在圖Y（2，2，m+2-1（m+1）δ）中取e=u1v1，由引理2.3和引理2.4，即得

結合（10）式，容易推知（11）也成立.

引理3.5設m（≥4）為偶數，1≤r∈N，δ=（r+1）p，p=|V（G）|，則有

證明 當m為偶數時，參考圖3.6，圖ΨT（δ，2，m+2-1mδ）即為ΨK（2，（m+1）+2-1（m+2）δ），故由（9）式即得（12）式.

當m為偶數時，此時m-1為偶數，d（u1）=r+di+1，d（vm）=3，這里di=d（vi），vi∈V（G），如圖3.6所示，在圖ΨT（2δ，2，m+2-1mδ）中取e=u1vm，由引理2.3和引理2.4，并運用（12）式，即得

由此可知（13）式成立.

引理3.6設m和r都是自然數，r≥1，δ=（r+1）p，p=|V（G）|，

4 因式分解定理

定理4.1設m（≥3）為奇數，1≤r∈N，δ=（r+1）p，p=|V（G）|，則有

證明 當m（≥3）為奇數時，注意到h（K1）=x，由引理2.5、（14）式和（11）式，即得

因此（18）式成立.

由引理2.5及（18）式，推知（19）式也成立.

定理4.2設k（≥2）是任意自然數而q（≥3）是奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則有

證明 設m是形如m=2k-1q-1的奇數，注意到λk=（2kq-1）+2k-1qδ，則計算可得

將上述頂點數代入（18）式，即得

由此可知（20）式成立；同理，將上述頂點數代入（19）式，即得（21）式.

定理4.3設k（≥2）是任意自然數而q（≥3）是奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則有

證明 對自然數k≥2作數學歸納法：當k=2時，由（20）式易推知

此時（22）式成立.假定結論對于k-1成立，對于k的情形，由引理2.5、（20）式及歸納假定即

得

即當k時結論也成立，故由數學歸納法原理知，對于任意的自然數k≥2，（22）式成立.

根據引理2.4及（22）式，容易推知（23）式成立.

定理4.4設k（≥2）是任意自然數而q（≥3）是奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則有

定理4.5設k（≥2）是任意自然數而q（≥3）是奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則有

上式兩端消去即得（26）式.

由引理2.4及（26）式，容易推知（27）式成立.

定理4.6設m（≥4）為偶數，1≤r∈N，δ=（r+1）p，p=|V（G）|，則有

故（28）式成立.

由引理2.4及（28）式，容易推知（29）式成立.

5 圖的色價性分析

在給出幾類圖的伴隨分解的基礎上，討論這些圖色等價性.

定理5.1設m（≥3）為奇數，1≤r∈N，δ=（r+1）p，p=|V（G）|，則有圖簇Y（2，2，（2m+ 1）+（m+1）δ）∪K1與ΨK（2，m+2-1（m+1）δ）∪Y（2，2，m+2-1（m+1）δ）二者的補圖是色等價的.

證明 根據（19）式知，Y（2，2，（2m+1）+（m+1）δ）∪K1=h（ΨK（2，m+2-1（m+ 1）δ）∪Y（2，2，m+2-1（m+1）δ））.由此及定義2.2可知，Y（2，2，（2m+1）+（m+1）δ）∪K1與ΨK（2，m+2-1（m+1）δ）∪Y（2，2，m+2-1（m+1）δ）圖簇是伴隨等價的，由此及引理2.2可知，補圖是色等價的.

定理5.2設k（≥2）是任意自然數而q（≥3）是奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則Y（2，2，λk）∪K1與ΨK（2，λk-1）∪Y（2，2，λk-1）圖簇的補圖是色等價的.

證明 根據（21）式知

由此及定義2.2可知Y（2，2，λk）∪K1與ΨK（2，λk-1）∪Y（2，2，λk-1）二者是伴隨等價的，由此及引理2.2可知，它們的補圖是色等價的.

仿此，根據定義2.2和引理2.2以及（23）、（27）、（29）三式，同法可證如下的結論.

定理5.3設?k∈N，k≥2而q（≥3）是正奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則Y（2，2，λk）∪（k-1）K1與Y（2，2，λ1）∪ΨK（2，λ1）∪ΨK（2，λ2）∪...∪ΨK（2，λk-1）圖簇二者的補圖是色等價的.

定理5.4設k（≥2）是任意自然數而q（≥3）是奇數，λk=（2kq-1）+2k-1qδ，δ=（r+1）p，p=|V（G）|，則圖簇Y（2，2，λk）與Y（2，2，λ1）∪CEG1+λ1∪CEG1+λ2∪···∪CEG1+λk-1二者的補圖是色等價的.

定理5.5設m（≥4）為偶數，1≤r∈N，δ=（r+1）p，p=|V（G）|，則圖簇Y（2，2，（2m+ 1）+（m+1）δ）∪與Y（1，2，（m-1）+2-1mδ）∪ΨT（2δ，m+2-1mδ）二者的補圖是色等價的.

［1］Bondy J A，Murty U S R.Graph Theory With Applications［M］.Amsterdam：North-Holland，1976.

［2］Bollobas B.Modern Graph Theory［M］.New York：Spinger-Verlag，1998.

［3］Chao C Y，Whitehead E G.On chromatic equivalance of graph［J］.Springer Lecture Note in Mathematics，1978，642：121-131.

［4］Koh K M，Teo K L.The search for chromatically unique graphs［J］.Graph Combin，1990，6：259-285.

［5］Biggs N.Algebraic Graph Theory［M］.Cambridge：Cambridge University Press，1974.

［6］Wang J F，Huang Q X，Liu R Y，Ye C F.A complete solution to the chromatic equivalence class of graph［J］.Discrete Math.，2008，308：3607-3623.

［7］Wang J F，Huang Q X，Liu R Y，Ye C F，et al.The chromatic equvalence class of graphdiscussiones math［J］.Graph Theory，2008，28（2）：189-218.

［8］Zhao H X，Li X L，Liu R Y.On problems and conjectures on adjointly equivalent graphs［J］.Discrete Mathematics，2005，295：203-212.

［9］劉儒英.兩類圖的色多項式［J］.科學通報，1987，32：1147-1148.

［10］張秉儒.圖的伴隨多項式的因式分解定理及應用［J］.數學學報，2005，48（1）：125-132.

The factorizations of adjoint polynomials of graphs of shape as Y（2，2，λ）and chromatically equivalence of their complements

Wang Yun1，Lu Dianjun2，Zhang Bingru2
（1.Qinghai University，Qinghai Xining810008，China；2.Department of Mathematics，Qinghai Normal University，Qinghai Xingning810008，China）

By unsing the properties of adjoint polynomials of graphs or even，we discuss the factorizations of adjoint polynomials of graphs Y（2，2，λ）∪K1（where m is odd）and Y（2，2，λ）∪EGδ（where m is even）.Let m=2Kq-1，letλn=（2nq-1）+2n-1qδ，we discuss the factorizations of adjoint polynomials of graphs Y（2，2，λk）∪（k-1）K1and Y（2，2，λk）.Further more，we prove chromatically equivalence of complements of these graphs.

adjoint polynomials，factorization，chromatically equivalence

O157.5

A

1008-5513（2015）04-0338-12

10.3969/j.issn.1008-5513.2015.04.002

2015-01-18.

青海省自然科學基金（2015-ZJ-724）；教育部春暉計劃（教外司留［2014］1310號）.

王云（1967-），碩士，副教授，研究方向：代數圖論，代數組合與密碼學.

2010 MSC:05C78