一個點并路的補圖的色等價圖類

李丹陽，馬海成

青海民族大學 數學與統計學院，西寧 810007

為了找到K1∪Pm(m≥2)的所有伴隨等價圖，按m+1所含的最大奇因數是1，3，5，9，15或其他奇數分為6種情形．為方便，用δ(G)表示圖G的所有不同構的伴隨等價圖的個數．δ(G)=1當且僅當G是伴隨唯一的．為方便讀者閱讀，下面列出文獻[16]中的12個等價橋：

(1)P2m+1～Pm∪Cm+1(m≥3)；

(2)T1，1，n～K1∪Cn+2(n≥2)；

(3)T1，2，n～K1∪Dn+3；

(4)P4～K1∪C3；

(5)K1∪P5～P2∪T1，1，1；

(6)C4～D4；

(7)P2∪C6～P3∪D5；

(8)P2∪C9～P5∪D6；

(9)K1∪C9～T1，1，1∪D6；

(10)P2∪C15～P5∪C5∪D7；

(11)K1∪C15～T1，1，1∪C5∪D7；

(12)C15∪D6～C5∪C9∪D7．

定理1若m+1=2n+1對某個正整數n成立，則

δ(K1∪Pm)=n2+1

證設H～K1∪Pm，H1是H的一個連通分支，使得β(H1)=β(Pm)，H=H1∪H2．

若H1=P7，由K1∪P7～H=P7∪H2得H2～K1，由K1伴隨唯一得到H2=K1．

若H1=C4，利用伴隨等價橋(1)，H=C4∪H2～K1∪P7～K1∪P3∪C4，從而得到H2～K1∪P3，再由文獻[16]中的推論3.2知K1∪P3伴隨唯一，所以H2=K1∪P3．

若H1=D4，利用伴隨等價橋(1)和(6)，H=D4∪H2～K1∪P7～K1∪P3∪D4，從而得到H2=K1∪P3．

若H1=T1，1，2，利用伴隨等價橋(1)和(2)，H=T1，1，2∪H2～K1∪P7～K1∪P3∪C4～P3∪T1，1，2，從而得到H2=P3．故δ(K1∪P7)=4．

假設結論對n-1(n≥3)，即m′+1=2n成立．由文獻[16]中的引理2.7 知H1=Pm，Cm2+1，T1，1，m2-1．

若H1=Pm，由K1∪Pm～H=Pm∪H2，得H2=K1．

若H1=Cm2+1，利用伴隨等價橋(1)，

H=Cm2+1∪H2～K1∪Pm～K1∪Pm2∪Cm2+1

若H1=T1，1，m2-1，利用伴隨等價橋(1)和(2)，

H=T1，1，m2-1∪H2～K1∪Pm～T1，1，m2-1∪Pm2

從而得到H2～Pm2．再由文獻[17]中的定理1 知這樣的H2共有n個．

故

若H1=P11，由H=P11∪H2～K1∪P11得H2=K1．

若H1=C6，利用伴隨等價橋(1)，H=C6∪H2～K1∪P11～K1∪P5∪C6，得H2～K1∪P5，又由n=2的情形知H2=K1∪P5，P2∪T1，1，1．

若H1=T1，1，4，利用伴隨等價橋(1)和(2)，H=T1，1，4∪H2～K1∪P11～K1∪P5∪C6～P5∪T1，1，4，從而得到H2～P5，由文獻[16]中的推論3.2知P5是伴隨唯一的，所以H2=P5．

若H1=D5，利用伴隨等價橋(1)，(5)和(7)，H=D5∪H2～K1∪P11～K1∪P5∪C6～P2∪T1，1，1∪C6～P3∪D5∪T1，1，1，從而得到H2～P3∪T1，1，1，又由文獻[16]中的推論3.2知P3∪T1，1，1是伴隨唯一的，所以H2=P3∪T1，1，1．

若H1=T1，2，2，利用伴隨等價橋(1)，(3)和(7)，H=T1，2，2∪H2～K1∪D5∪H2～K1∪P11～K1∪P5∪C6～P2∪T1，1，1∪C6～P3∪D5∪T1，1，1，從而得到K1∪H2～P3∪T1，1，1，由于P3∪T1，1，1是伴隨唯一的，所以這樣的H2是不存在的．故δ(K1∪P11)=5．

假設結論對n-1(n≥3)，即m′+1=3×2n-2成立．由文獻[16]中的引理2.7知H1=Pm，Cm2+1，T1，1，m2-1．同類似，我們得到H2～K1，K1∪Pm2，Pm2．由歸納假設和文獻[17]中的定理1 知，這樣的H2分別有1 個，個或n-2個，故

若H1=P9，由H=P9∪H2～K1∪P9得H2=K1．

H1=C5，利用伴隨等價橋(1)，H=C5∪H2～K1∪P9～K1∪P4∪C5，得H2～K1∪P4，又由n=1的情形知H2=K1∪P4，2K1∪C3．

若H1=T1，1，3，利用伴隨等價橋(1)和(2)，H=T1，1，3∪H2～K1∪P9～K1∪P4∪C5～P4∪T1，1，3，得H2～P4，又由文獻[17]中的定理1得H2=P4，K1∪C3．故δ(K1∪P9)=5．

假設結論對n-1(n≥3)，即m′+1=5×2n-2成立．由文獻[16]中的引理2.7 知H1=Pm，Cm2+1，T1，1，m2-1．同類似，我們得到H2～K1，K1∪Pm2，Pm2．由歸納假設和文獻[17]中的定理1 知，這樣的H2分別有1個，(n-1)2+1個或2(n-1)個，故

δ(K1∪Pm)=1+(n-1)2+1+2(n-1)=n2+1

若H1是前4個圖，相應地，H2～K1，K1∪P8，P8，P8∪T1，1，1，由文獻[16]中的推論3.2知這些圖都是伴隨唯一的，所以H2=K1，K1∪P8，P8，P8∪T1，1，1．

若H1=T1，2，3，利用伴隨等價橋(1)，(3)和(9)，H=T1，2，3∪H2～K1∪D6∪H2～K1∪P17～K1∪P8∪C9～P8∪T1，1，1∪D6，得K1∪H2～P8∪T1，1，1，又由于P8∪T1，1，1是伴隨唯一的，所以這樣的H2是不存在的．故δ(K1∪P17)=4．

假設結論對n-1(n≥3)，即m′+1=9×2n-2成立．由文獻[16]中的引理2.7知H1=Pm，Cm2+1，T1，1，m2-1．同類似，我們得到H2～K1，K1∪Pm2，Pm2．由歸納假設和文獻[17]中的定理1 知，這樣的H2分別有1個，個或n-1個，故

若m+1=2n+1對某個正整數n成立，或m+1=2n-1×(2k-1)(k≠2)對某對正整數n，k成立，令

Ω1={Pm1，Pm2∪Cm2+1，Pm3∪Cm2+1∪Cm3+1，…，Pmn∪Cm2+1∪Cm3+1∪…∪Cmn+1}

若m+1=3×2n-1對某個正整數n成立，令

Ω2={Pm1，Pm2∪Cm2+1，Pm3∪Cm2+1∪Cm3+1，…，Pmn-1∪Cm2+1∪Cm3+1∪…∪Cmn-1+1}

若m+1=5×2n-1對某個正整數n成立，令

若m+1=2n+1對某個正整數n成立，則

若m+1=3×2n-1對某個正整數n成立，則

若m+1=5×2n-1對某個正整數n成立，則[Pm]=Ω1∪Ω3；

若m+1=2n-1×(2k+1)(k≠1，2)對某對正整數n和k成立，則[Pm]=Ω1．

若m+1=2n+1對某個正整數n成立，或m+1=2n-1×(2k-1)(k≠2)對某對正整數n，k成立，由等價橋(2)我們知道，集合Ω1中的每一個含有圈分支的圖中的每一個圈與一個孤立點K1相遇就會等價于一個T-形分支．令

若m+1=2n+1對某個正整數n成立，由等價橋(6)，Θ1中的圖K1∪P3∪C4∪C8∪…∪Cm2+1等價于K1∪P3∪D4∪C8∪…∪Cm2+1，再利用等價橋(2)使得圖K1∪P3∪D4∪Cm2+1∪…∪Cmn-1+1中的每一個圈分支與一個孤立點K1相遇就會等價于一個T-形分支，令

若m+1=3×2n-1，n≥3．由等價橋(2)知集合Ω2中的每一個含有圈分支的圖中的每一個圈與一個孤立點K1相遇就會等價于一個T-形分支．令

若m+1=5×2n-1，K1∪Pm的等價圖除集合Θ1中的圖外，還有集合{K1∪H：H∈Ω3}中的圖．由等價橋(2)，{K1∪H：H∈Ω3}中的圖2K1∪C3∪C5∪…∪Cm2+1中除C3外的任何兩個圈與兩個孤立點2K1相遇就會等價于兩個T-形分支．令

Δ2={C3∪T1，1，3∪T1，1，8∪…∪Cm2+1，C3∪C5…∪T1，1，m3-1∪T1，1，m2-1}

若m+1=9×2n-1，n≥2，K1∪Pm的等價圖除集合Θ1中的圖外，還包含圖P8∪T1，1，1∪D6∪C18∪…∪Cm2+1．由等價橋(9)，集合Θ1中的圖K1∪P8∪C9∪…∪Cm2+1等價于圖P8∪T1，1，1∪D6∪C18∪…∪Cm2+1．

若m+1=15×2n-1，n≥2，K1∪Pm的等價圖除集合Θ1中的圖外，還包含圖P14∪T1，1，1∪C5∪D7∪C30∪…∪Cm2+1．由等價橋(11)，集合Θ1中的圖K1∪P14∪C15∪…∪Cm2+1等價于圖P14∪T1，1，1∪C5∪D7∪C30∪…∪Cm2+1．

于是，我們得到下面的結果：

定理2若m+1=2n+1對某個正整數n成立，則

[K1∪Pm]=Θ1∪{K1∪H：H∈Ω3}∪Δ2

證由文獻[16]中的等價變換規律，這些圖均等價于K1∪Pm，且圖的個數也等于δ(K1∪Pm)．