2K1∪In的匹配等價圖類

高尚，馬海成

青海民族大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院，西寧 810007

本文僅考慮有限無向的簡單圖.設(shè)G是一個n階圖，G的一個匹配是指G的一個生成子圖，它的每一個分支是孤立邊或者孤立點，k-匹配是指其中有k條邊的匹配.文獻(xiàn)[1]定義了圖G的匹配多項式為

這里，p(G，k)是G的所有k-匹配的數(shù)目，并且約定p(G，0)=1.在文中為了方便，將μ(G，x)簡記為μ(G).若圖G和H有μ(G，x)=μ(H，x)，則稱圖G和H是匹配等價的，記為G～H.設(shè)G是一個圖，以[G]表示圖G的匹配等價圖的集合，以σ(G)表示集合[G]的元的個數(shù)，即|[G]|.若σ(G)=1，稱圖G是匹配唯一的.

文獻(xiàn)[14]的定理1給出了K1∪Pm的匹配等價圖類.為了方便，我們將與K1∪Pm的匹配等價的圖的集合記為Φ1，則|Φ1|=σ(K1∪Pm).

文獻(xiàn)[15]的定理1和定理2給出了2K1∪Pm的匹配等價圖類.通過觀察我們發(fā)現(xiàn)，除了m+1=3×2n-1(n≥3)的情形外，2K1∪Pm的每一個匹配等價圖包含且僅包含一個路分支.而當(dāng)m+1=3×2n-1(n≥3)時，2K1∪Pm的匹配等價圖中含有Q(2，1)分支的等價圖是：Q(2，1)∪H，H∈Δ4，其中的每一個H有且恰有兩個不同的路分支.用Φ2表示2K1∪Pm的每一個匹配等價圖中刪去一條路分支后得到的圖的集合.于是

為了方便，本文用σ(G，H)表示圖G的所有匹配等價圖中含有分支H的等價圖的個數(shù).

引理1若m+1=3×2n-1對某個正整數(shù)n成立，則

證H～3K1∪Pm，H1是H的連通分支，使得

M1(H1)=M1(Pm)H=H1∪H2

對n用數(shù)學(xué)歸納法.當(dāng)n=1時，結(jié)論明顯.當(dāng)n=2時，由文獻(xiàn)[16]的引理2，3和4得，H1=P5，C3，T1，1，1，相應(yīng)地，H2～3K1，3K1∪P2，2K1∪P2，則

σ(3K1∪P5，P2)=0+1+1=2

σ(3K1∪P5，P2∪P3)=0+0+0=0

當(dāng)n=3時，由文獻(xiàn)[16]的引理2，3和4得，H1=P11，C6，T1，1，4，Q(2，1)，T1，2，2，相應(yīng)地，H2～3K1，3K1∪P5，2K1∪P5，2K1∪P3∪P5，2K1∪P3∪C3，由文獻(xiàn)[16]的引理10得

σ(3K1∪P11，P2)=0+2+2+2+0=6

σ(3K1∪P11，P2∪P3)=0+0+0+2+0=2

當(dāng)n≥4時，由文獻(xiàn)[16]的引理2，3和4得，H1=Pm，Cm2+1，T1，1，m2-1(m2+1=3×2n-2)，相應(yīng)地，H2～3K1，3K1∪Pm2，2K1∪Pm2，由文獻(xiàn)[16]的引理10得

設(shè)H～3K1∪Pm，H1是H的連通分支，使得

M1(H1)=M1(Pm)H=H1∪H2

(a)m+1=2n+1.當(dāng)n=1時，σ(3K1∪P3，P2)=0，假設(shè)結(jié)論對m2+1=2n成立，且對n用數(shù)學(xué)歸納法，H1=Pm，Cm2+1，T1，1，m2-1，相應(yīng)地，H2～3K1，3K1∪Pm2，2K1∪Pm2，則

σ(3K1∪Pm，P2)=0+0+0=0

(b)m+1=9×2n-1.當(dāng)n=1時，σ(3K1∪P8，P2)=0.當(dāng)n=2時，H1=P17，C9，T1，1，7，T1，2，3，相應(yīng)地，H2～3K1，3K1∪P8，2K1∪P8，2K1∪C3∪P8，則

σ(3K1∪P17，P2)=0+0+0+0=0

假設(shè)結(jié)論對m2+1=9×2n-2成立，且對n用數(shù)學(xué)歸納法，H1=Pm，Cm2+1，T1，1，m2-1，相應(yīng)地，H2～3K1，3K1∪Pm2，2K1∪Pm2，則

σ(3K1∪Pm，P2)=0+0+0=0

(c)m+1=15×2n-1.當(dāng)n=1時，σ(3K1∪P14，P2)=0.當(dāng)n=2時，H1=P29，C15，T1，1，13，T1，2，4，相應(yīng)地，H2～3K1，3K1∪P14，2K1∪P14，2K1∪C3∪P14，則

σ(3K1∪P29，P2)=0+0+0+0=0

假設(shè)結(jié)論對m2+1=15×2n-2成立，且對n用數(shù)學(xué)歸納法，H1=Pm，Cm2+1，T1，1，m2-1，相應(yīng)地，H2～3K1，3K1∪Pm2，2K1∪Pm2，則

σ(3K1∪Pm，P2)=0+0+0=0

(d)m+1=2n-1(2k+1)，k(≠0，1，4，7)為整數(shù).當(dāng)n=1時，σ(3K1∪P2k，P2)=0.假設(shè)結(jié)論對m2+1=2n-2(2k+1)成立，且對n用數(shù)學(xué)歸納法，H1=Pm，Cm2+1，T1，1，m2-1，相應(yīng)地，H2～3K1，3K1∪Pm2，2K1∪Pm2，則

σ(3K1∪Pm，P2)=0+0+0=0

引理2若m+1=3×2n-1對某個正整數(shù)n成立，則3K1∪Pm的匹配等價圖中含有分支P2的圖是下面的圖：

2K1∪P2∪T1，1，1∪C6∪C12∪…∪C3×2n-2，…，2K1∪P2∪C3∪C6∪C12∪…∪T1，1，3×2n-2-2；

K1∪P2∪T1，1，1∪T1，1，4∪C12∪…∪C3×2n-2，…，K1∪P2∪C3∪C6∪C12∪…∪T1，1，3×2n-3-2∪T1，1，3×2n-2-2；

P2∪T1，1，1∪T1，1，4∪T1，1，10∪…∪C3×2n-2，…，P2∪C3∪C6∪C12∪…∪T1，1，3×2n-4-2∪T1，1，3×2n-3-2∪T1，1，3×2n-2-2；

2K1∪P2∪P3∪Q(2，1)∪C3∪C12∪…∪C3×2n-2；

K1∪P2∪P3∪Q(2，1)∪T1，1，1∪C12∪…∪C3×2n-2，…，K1∪P2∪P3∪Q(2，1)∪C3∪C12∪…∪T1，1，3×2n-2-2；

P2∪P3∪Q(2，1)∪T1，1，1∪T1，1，10∪…∪C3×2n-2，…，P2∪P3∪Q(2，1)∪C3∪C12∪…∪T1，1，3×2n-3-2∪T1，1，3×2n-2-2.

引理3若m≥2是整數(shù)，σ(3K1∪Pm，2P2)=0，σ(3K1∪Pm，P2∪P4)=0.

證由引理1和引理2，結(jié)果顯然.

為了方便，用Φ3表示3K1∪Pm的含有分支P2的所有匹配等價圖中刪去P2后得到的圖的集合，即引理2中的每張圖刪去P2后得到的圖的集合，則|Φ3|=σ(3K1∪Pm，P2).用Φ4表示3K1∪Pm的含有分支P2∪P3的所有匹配等價圖中刪去P2∪P3后得到的圖的集合，即引理2中的每張圖刪去P2∪P3后得到的圖的集合，則|Φ4|=σ(3K1∪Pm，P2∪P3).

為了找到2K1∪Im(m≥6)的匹配等價圖類，按m-3所含最大奇因數(shù)是1，3，9，15或其他奇數(shù)分為5類.

定理1若m-3=2n+1對某個正整數(shù)n成立，則

證設(shè)H～2K1∪Im，由M1(H)=2及文獻(xiàn)[16]的引理2(2)知，H必有一連通分支H1∈Ω2，H=H1∪H2.

(a) 若H1=It(t≥6)，則

2K1∪Im～H=It∪H2

兩邊并Pm-4，利用文獻(xiàn)[16]的引理13(8)得

Pm-4∪2K1∪Im～Pm-4∪It∪H2～Pt-4∪Im∪H2

則

2K1∪Pm-4～Pt-4∪H2

由文獻(xiàn)[15]的定理1和定理2知，這樣的H2∈Φ2.

(b) 若H1=K1，4，則

2K1∪Im～H=K1，4∪H2

兩邊并Pm-4∪P2，利用文獻(xiàn)[16]的引理13(7)，(8)得

Pm-4∪P2∪2K1∪Im～Pm-4∪P2∪K1，4∪H2～Pm-4∪K1∪I6∪H2～K1∪P2∪Im∪H2

則

K1∪Pm-4～H2

由文獻(xiàn)[14]的定理1知，這樣的H2∈Φ1.

(c) 若H1=Q(2，2)，Q(3，1)(～Q(2，2))，T2，2，2(～P2∪Q(2，2))，T1，3，3(～P3∪Q(2，2))，T1，2，5(～P4∪Q(2，2))，均可設(shè)

2K1∪Im～H=Q(2，2)∪H2

兩邊并K1∪Pm-4，利用文獻(xiàn)[16]的引理13(3)，(8)得

3K1∪Pm-4∪Im～K1∪Pm-4∪Q(2，2)∪H2～Pm-4∪I6∪H2～P2∪Im∪H2

則

3K1∪Pm-4～P2∪H2.

(a) 若H1=It(t≥6)，與的情形(a)類似，這樣的H2∈Φ2.

(b) 若H1=K1，4，與的情形(b)類似，這樣的H2∈Φ1.

(c) 若H1=Q(2，2)，則

2K1∪Im～H=Q(2，2)∪H2

3K1∪Pm-4～P2∪H2

由引理2知，這樣的H2∈Φ3.

(d) 若H1=Q(3，1)，由Q(3，1)～Q(2，2)，與情形(c)類似，這樣的H2∈Φ3.

(e) 若H1=T1，3，3，由文獻(xiàn)[16]的引理13(5)得

2K1∪Im～H=T1，3，3∪H2～P3∪Q(2，2)∪H2

3K1∪Pm-4～P2∪P3∪H2

由引理1和引理2知：當(dāng)n≤2時，這樣的H2不存在；當(dāng)n≥3時，這樣的H2∈Φ4.

(f) 若H1=T2，2，2.由文獻(xiàn)[16]的引理13(4)得

2K1∪Im～H=T2，2，2∪H2～P2∪Q(2，2)∪H2

3K1∪Pm-4～2P2∪H2

由引理3知，這樣的H2不存在.

(g) 若H1=T1，2，5，由文獻(xiàn)[16]的引理13(6)得

2K1∪Im～H=T1，2，5∪H2～P4∪Q(2，2)∪H2

3K1∪Pm-4～P2∪P4∪H2

由引理3知，這樣的H2不存在.

證由文獻(xiàn)[16]的引理14，結(jié)論顯然.