王云，蘆殿軍，張秉儒

（1.青海大學(xué)，青海 西寧810006；2.青海師范大學(xué)數(shù)學(xué)系，青海 西寧810008）

Y（2，2，λ）形圖的伴隨多項(xiàng)式的分解及其補(bǔ)圖的色等價(jià)性

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

（1.青海大學(xué)，青海 西寧810006；2.青海師范大學(xué)數(shù)學(xué)系，青海 西寧810008）

構(gòu)造了兩類(lèi)圖簇Y（2，2，λ）∪K1（m為奇數(shù)）和Y（2，2，λ）∪EGδ（m為偶數(shù)）.運(yùn)用圖的伴隨多項(xiàng)式，討論了這兩類(lèi)圖簇的伴隨多項(xiàng)式的因式分解式，（m=2k-1q-1，λk=（2kq-1）+2k-1qδ），研究了圖簇Y（2，2，λk）∪（k-1）K1和Y（2，2，λk）的伴隨多項(xiàng)式的因式分解式，進(jìn)而證明了這些圖的補(bǔ)圖的色等價(jià)性.

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

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

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

新的圖簇，且運(yùn)用圖的伴隨多項(xiàng)式的性質(zhì)，主要討論了

圖簇的伴隨多項(xiàng)式及其因式分解式，當(dāng)m=2kq-1，λn=（2nq-1）+2n-1qr時(shí)，討論了圖簇Y（2，2，λk）∪（k-1）K1和Y（2，2，λk）的伴隨多項(xiàng)式的因式分解式，并且證明了上述圖簇的補(bǔ)圖的色等價(jià)性，確定了它們的補(bǔ)圖的色等價(jià)圖的構(gòu)成規(guī)律.

2 圖的伴隨多項(xiàng)式的概念

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

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

定義2.1［5］設(shè)G是p階圖，則圖G的多項(xiàng)式

稱(chēng)為簡(jiǎn)單圖G的伴隨多項(xiàng)式，h（G，x）可以簡(jiǎn)記為h（G）.圖G的每個(gè)分支或是K1或是K2的生成子圖稱(chēng)為圖G的一個(gè)匹配，圖G的一個(gè)K-匹配就是含有k條邊的匹配，由G的理想子圖的個(gè)數(shù)bi（G）的定義即得如下的.

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

定義2.2稱(chēng)圖G與H是伴隨等價(jià)的，若h（G，x）=h（H，x），稱(chēng)圖G是伴隨唯一的，若從h（G，x）=h（H，x）推出G與H同構(gòu)，記為H≌G.

引理2.2［6］圖G與H是伴隨等價(jià)的當(dāng)且僅當(dāng)和是色等價(jià)的；圖G是伴隨唯一的當(dāng)且僅當(dāng)是色唯一的.

下面給出常用到圖的伴隨多項(xiàng)式h（G，x）的基本性質(zhì).

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

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

設(shè)G是任意的連通圖，其伴隨多項(xiàng)式為h（G，x），以下簡(jiǎn)記為h（G）.根據(jù)引理2.4，易得下面引理成立.

引理2.5設(shè)G和H是任意的兩個(gè)圖，K1是一個(gè)孤立點(diǎn)，n≥2是任意的自然數(shù)，則有

引理2.6［10］設(shè)n≥2是自然數(shù)，Sn表示具有n個(gè)頂點(diǎn)的星圖，則有

3 幾類(lèi)新圖的伴隨多項(xiàng)式

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

圖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設(shè)m（≥3）是奇數(shù)，r是任意自然數(shù)，r≥1，δ=（r+1）p，p=|V（G）|，則有

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

證明 參考圖3.3，m是偶數(shù)，則m+1是奇數(shù)，故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設(shè)m（≥3）為奇數(shù)，r是自然數(shù)，r≥1，δ=（r+1）p，p=|V（G）|，則有

證明 當(dāng)m為奇數(shù)時(shí)，此時(shí)m+1與m-1均為偶數(shù)，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，即得

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

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

證明 當(dāng)m為偶數(shù)時(shí)，參考圖3.6，圖ΨT（δ，2，m+2-1mδ）即為ΨK（2，（m+1）+2-1（m+2）δ），故由（9）式即得（12）式.

當(dāng)m為偶數(shù)時(shí)，此時(shí)m-1為偶數(shù)，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，并運(yùn)用（12）式，即得

由此可知（13）式成立.

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

4 因式分解定理

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

證明 當(dāng)m（≥3）為奇數(shù)時(shí)，注意到h（K1）=x，由引理2.5、（14）式和（11）式，即得

因此（18）式成立.

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

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

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

將上述頂點(diǎn)數(shù)代入（18）式，即得

由此可知（20）式成立；同理，將上述頂點(diǎn)數(shù)代入（19）式，即得（21）式.

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

證明 對(duì)自然數(shù)k≥2作數(shù)學(xué)歸納法：當(dāng)k=2時(shí)，由（20）式易推知

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

得

即當(dāng)k時(shí)結(jié)論也成立，故由數(shù)學(xué)歸納法原理知，對(duì)于任意的自然數(shù)k≥2，（22）式成立.

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

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

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

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

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

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

故（28）式成立.

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

5 圖的色價(jià)性分析

在給出幾類(lèi)圖的伴隨分解的基礎(chǔ)上，討論這些圖色等價(jià)性.

定理5.1設(shè)m（≥3）為奇數(shù)，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）δ）二者的補(bǔ)圖是色等價(jià)的.

證明 根據(jù)（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）δ）圖簇是伴隨等價(jià)的，由此及引理2.2可知，補(bǔ)圖是色等價(jià)的.

定理5.2設(shè)k（≥2）是任意自然數(shù)而q（≥3）是奇數(shù)，λ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）圖簇的補(bǔ)圖是色等價(jià)的.

證明 根據(jù)（21）式知

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

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

定理5.3設(shè)?k∈N，k≥2而q（≥3）是正奇數(shù)，λ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）圖簇二者的補(bǔ)圖是色等價(jià)的.

定理5.4設(shè)k（≥2）是任意自然數(shù)而q（≥3）是奇數(shù)，λ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二者的補(bǔ)圖是色等價(jià)的.

定理5.5設(shè)m（≥4）為偶數(shù)，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δ）二者的補(bǔ)圖是色等價(jià)的.

［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］劉儒英.兩類(lèi)圖的色多項(xiàng)式［J］.科學(xué)通報(bào)，1987，32：1147-1148.

［10］張秉儒.圖的伴隨多項(xiàng)式的因式分解定理及應(yīng)用［J］.數(shù)學(xué)學(xué)報(bào)，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.

青海省自然科學(xué)基金（2015-ZJ-724）；教育部春暉計(jì)劃（教外司留［2014］1310號(hào)）.

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

2010 MSC:05C78