一類笛卡兒積圖中可去邊的研究

馬云鳳

（閩南師范大學數(shù)學與統(tǒng)計學院,福建 漳州 363000）

記圖G的頂點集和邊集分別為V(G)和E(G).設M是E(G)的一個子集，若該邊子集中的任意兩條邊在圖G中均不相鄰，則稱M為圖G的匹配.若匹配M的某條邊與頂點v關聯(lián)，則稱頂點v是M飽和的.若圖G的每個頂點均為M飽和的，則稱M為圖G的完美匹配.引入匹配覆蓋圖的定義：若圖G為有兩個以上頂點的連通圖，并且其任意一條邊都屬于某個完美匹配，則稱圖G為匹配覆蓋圖.圖G為匹配覆蓋圖，e為G中一條邊，若G-e仍為匹配覆蓋圖，則e為圖G的可去邊.

假設k是一個滿足的整數(shù)，圖G是一個有完美匹配的連通圖，若圖G中任意包含k條邊的匹配都屬于一個完美匹配，則稱圖G是k-可擴圖.匹配覆蓋圖顯然就是1-可擴圖.容易看出對于2-可擴圖，所有的邊都是可去邊.1992年，Gy?ri 等[1]證明了若G1是一個k-可擴圖,G2是一個l-可擴圖，則它們的笛卡兒乘積圖G1×G2是(k+l+1)-可擴圖，其中；若G1是一個k-可擴圖，G2是一個連通圖，則它們的笛卡兒乘積圖G1×G2是(k+1)-可擴圖，其中1≤k≤一個頂點數(shù)至少為2m+2n+2 的有完美匹配的連通圖被稱為E(m,n)的，如果對于任意兩個無公共邊的匹配M和N，存在完美匹配F滿足M?F且N∩F=?，其中|M|=m，|N|=n.注意到圖G是m-可擴的當且僅當它是E(m,0)的.2017年Aldred 等[2]證明了若m≥0 且G是E(m,1)的，則G×P2是E(m+1,0)和E(m,2)的.2-可擴的二部圖，稱為brace；三連通雙臨界圖，稱為brick，其中，雙臨界圖是指去掉任意兩個頂點后存在完美匹配的圖.1983年Lovász[3]證明了每個brick（除K4和Cˉ6)都有一條可去邊.1999年Lucchesi 等[4]證明了每個brick（除K4和Cˉ6）至少有Δ-2 條可去邊，其中Δ是圖的最大度.2015年，Carvalho等[5]證明了在頂點數(shù)至少為六的brace中，每一條邊都為可去邊.

設圖G的頂點集V(G)={v1,v2,…,vn}，G1,G2,…,Gl是l個與G同構的圖，其頂點集分別為{v11,v21,…,vn1},{v12,v22,…,vn2},…,{v1l,v2l,…,vnl}，圖H=G×Pl是將G1,G2,…,Gl用邊v1iv1,i+1,v2iv2,i+1,…,vnivn,i+1,i=1,…,l-1連接得到.記[l]=1,…,l-1.若圖G為有完美匹配的圖，取其一個完美匹配，記為M，M在圖Gi中的限制，記為Mi（即M與Gi的交為Mi），i∈[l].對于任一有完美匹配的連通圖G（δ(G)≥2）和包含l個頂點的路Pl（l≥4），證明了它們的笛卡兒乘積圖G×Pl為匹配覆蓋圖，且每條邊都是可去邊，其中δ(G)是圖G的最小度.

1 主要結論與證明

定理1設圖G為有完美匹配的連通圖，且δ(G)≥2，Pl為包含l個頂點的路（l≥4），則圖G×Pl為匹配覆蓋圖.

證明下面將根據(jù)l的奇偶性進行分類討論.

情況1l為偶數(shù)，設l=2m.

設E其結構如圖1所示.

圖1 Ea和Eb的結構Fig.1 The structure of Ea and Eb

情況1.1e∈Ea，容易驗證Ea是圖G×P2m的完美匹配，并且e∈Ea.

情況1.2e∈Eb，不妨設e=vs,2ivs,2i+1,容易驗證Mb=(Ea-E[G2i-1,G2i]-E[G2i+1,G2i+2]) ∪M2i-1∪E[G2i,G2i+1]∪M2i+2是圖G×P2m的完美匹配，并且e∈Mb.

情況1.3e∈不妨設e=vs,2ivt,2i，容易驗證是圖G×P2m的完美匹配，并且e∈Mc.

所以，G×P2m中任意一條邊都屬于某個完美匹配.

情況2l為奇數(shù)，設l=2m+1.

Ea和Eb的定義同上.記Eb*=Eb∪E[G2m,G2m+1]，則根據(jù)G×P2m+1的對稱性可知，Ea和Eb*這兩類邊有類似的結構，E(G2m+1)和這兩類邊有類似的結構，因此，根據(jù)e在G×P2m+1的位置，可以只考慮以下3種情況.

情況2.1e∈Ea，容易驗證Ea∪M2m+1是圖G×P2m+1的完美匹配，并且e∈Ea∪M2m+1.

情況2.2e∈不妨設e=vs,2ivt,2i，容易驗證Mc∪M2m+1是圖G×P2m+1的完美匹配，并且e∈Mc∪M2m+1.

情況2.3e∈不妨設e=vs,2i-1vt,2i-1，同理，容易驗證Mc∪M2m+1是圖G×P2m+1的完美匹配，并且e∈Mc∪M2m+1.

所以，G×P2m+1中任意一條邊都屬于某個完美匹配.

綜上所述，G×Pl中任意一條邊都屬于某個完美匹配,即G×Pl為匹配覆蓋圖.

定理2設圖G為有完美匹配的連通圖，且δ(G)≥2，Pl為包含l個頂點的路（l≥4），則圖G×Pl的每條邊都是可去邊.

證明只需證明對?e′∈E(G×Pl)，G×Pl-e′中任意一條邊都屬于某個完美匹配.下面將根據(jù)l的奇偶性進行分類討論.本定理的證明中出現(xiàn)的Ea、Eb、Eb*、Mb、Mc皆如定理一中證明所定義.

情況1l為偶數(shù)，設l=2m.

當l為偶數(shù)，根據(jù)e在G×P2m-e′的位置，可以只考慮以下3種情況.

情況1.1e∈Ea，若e′?Ea，容易驗證Ea是圖G×P2m-e′的完美匹配，并且e∈Ea.否則，e′∈Ea，不妨設e′=vj,2i-1vj,2i且vk∈NG(vj)，則C1=vj,2i-1vj,2ivk,2ivk,2i-1vj,2i-1是一個Ea交錯圈，容易驗證E(C1)ΔEa是圖G×P2me′的完美匹配，并且e∈E(C1)ΔEa.

情況1.2e∈Eb，不妨設e=vs,2ivs,2i+1，若e′?Mb，容易驗證Mb是G×P2m-e′的完美匹配，且e∈Mb；否則，e′∈Mb=(Ea-E[G2i-1,G2i]-E[G2i+1,G2i+2]) ∪M2i-1∪E[G2i,G2i+1]∪M2i+2，即e′∈(Ea-E[ ]

G2i-1,G2i-E[G2i+1,G2i+2])∪E[G2i,G2i+1]或e′∈M2i-1∪M2i+2.

情況ae′∈(Ea-E[G2i-1,G2i]-E[G2i+1,G2i+2]) ∪E[G2i,G2i+1]，則根據(jù)本定理情況1.1 的方法，G×P2me′存在完美匹配包含e.

情況be′∈M2i-1∪M2i+2，不妨設e′∈M2i+2且e′=vj,2i+2vk,2i+2，則C2=vj,2ivj,2i+1vj,2i+2vk,2i+2vk,2i+1vk,2ivj,2i是一個Mb交錯圈.若e?C2，容易驗證E(C2)ΔMb是圖G×P2m-e′的完美匹配，并且e∈E(C2)ΔMb（局部結構如圖2所示）.否則，e∈C2，不妨設e=vk,2ivk,2i+1（即s=k），由于δ(G)≥2，所以存 在 頂點vl∈NG(vk).令C3=vk,2i-1vk,2ivk,2i+1vk,2i+2vl,2i+2vl,2i+1vl,2ivl,2i-1vk,2i-1，顯然C3是一個Ea交錯圈，容易驗證E(C3)ΔEa是圖G×P2me′的完美匹配，并且e∈E(C3)ΔEa（局部結構如圖3所示）.

圖2 E(C2)ΔMb的局部結構Fig.2 Part of E(C2)ΔMb

圖3 E(C3)ΔEa的局部結構Fig.3 Part of E(C3)ΔEa

情況1.3e∈不妨設e=vs,2ivt,2i.若e′?Mc，容易驗證Mc是G×P2m-e′的完美匹配，并且e∈Mc.否則，e′∈Mc=(Ea-{vs,2i-1vs,2i,vt,2i-1vt,2i}) ∪{vs,2i-1vt,2i-1,vs,2ivt,2i}，即e′∈Ea-{vs,2i-1vs,2i,vt,2i-1vt,2i}或e′∈{vs,2i-1vt,2i-1,vs,2ivt,2i}.

情況ce′∈Ea-{vs,2i-1vs,2i,vt,2i-1vt,2i}，則根據(jù)本定理情況1.1的方法，G×P2m-e′存在完美匹配包含e.

情況de′∈{vs,2i-1vt,2i-1,vs,2ivt,2i}，又因為e′≠e，所以e′=vs,2i-1vt,2i-1,i∈[m].當i∈[m-1]時，由于δ(G)≥2，l≥4，所以存在頂點vj∈NG(vs),vk∈NG(vt).令C4=vj,2i-1vj,2ivj,2i+1vj,2i+2vs,2i+2vs,2i+1vt,2i+1vt,2i+2vk,2i+2vk,2i+1vk,2i vk,2i-1vt,2i-1vt,2ivs,2ivs,2i-1vj,2i-1，顯然C4是一個Ea交錯圈，容易驗證E(C4)ΔEa是圖G×P2m-e′的完美匹配，并且e∈E(C4)ΔEa（局部結構如圖4所示）.當i=m時，有e′=vs,2m-1vt,2m-1，e=vs,2mvt,2m，同 時，C5=vs,2m-3vs,2m-2vs,2im-1vs,2mvt,2mvt,2m-1vt,2m-2vt,2m-3vs,2m-3是一個Ea交錯圈，容易驗證E(C5)ΔEa是圖G×P2m-e′的完美匹配，并且e∈E(C5)ΔEa（局部結構如圖5所示）.

圖4 E(C4)ΔEa的局部結構Fig.4 Part of E(C4)ΔEa

圖5 E(C5)ΔEa的局部結構Fig.5 Part of E(C5)ΔEa

所以，對?e′∈E(G×P2m)，G×P2m-e′中任意一條邊都屬于某個完美匹配.

情況2m為奇數(shù)，設l=2m+1.

首先考慮l≥7 的情況.在定理1 的證明過程中，當l為奇數(shù)時，根據(jù)e在G×P2m+1的位置，只考慮了和這三種情況.根據(jù)G×P2m+1的對稱性可知，E(G2m) 和這兩類邊有類似的結構，E(G2m-1)和這兩類邊有類似的結構.因此，可以只考慮和這三種情況.在以上任一種情況中，若e′∈E(G2m+1)，根據(jù)本定理情況1.2 中情況b 的方法（局部結構類似于圖2所示），G×P2m+1-e′存在完美匹配包含e.否則e′?E(G2m+1)，即e′∈E[G2m,G2m+1]或e′∈E(G×P2m).當e′∈E[G2m,G2m+1]時，顯然G×P2m+1-e′存在完美匹配包含e.當e′∈E(G×P2m)時，根據(jù)l為偶數(shù)時的結論，G×P2m-e′存在完美匹配包含e，則G×P2m+1-e′存在完美匹配包含e.

其次考慮l=5 的情況.此時E(G2m-1)=E(G3)，結合l≥7 的證明可知，需要考慮e∈Ea和e∈E(G1)∪E(G2)∪E(G3)的情況.e∈Ea和e∈E(G1)∪E(G2)的情況同l≥7，只需考慮e∈E(G3).設e=vs,3vt,3，根據(jù)定理一情況2.3，容易驗證是G×P5的完美匹配，并且e∈Mc∪M5.若e′?Mc∪M5，顯然G×P5-e′存在完美匹配包含e.否則，e′∈Mc∪M5，即e′∈Mc或e′∈M5.

情況2.1e′∈Mc，根據(jù)l為偶數(shù)時的結論，G×P4-e′存在完美匹配包含e，則G×P5-e′存在完美匹配包含e.

情況2.2e′∈M5，若e′=vk,5vs,5（或e′=vj,5vt,5），其中vk,5是vs,5的異于vt,5的鄰點（或vj,5是vt,5的異于vs,5的鄰點），容易驗證是G×P2m+1-e′的完美匹配，并且e∈M′（如圖6所示）.否則，e′∈M5-vk,5vs,5-vj,5vt,5，根據(jù)本定理情況1.2中情況b的方法（局部結構類似于圖2所示），G×P2m+1-e′存在完美匹配包含e.

圖6 M′的結構Fig.6 The structure of M′

所以，對?e′∈E(G×P2m+1)，G×P2m+1-e′中任意一條邊都屬于某個完美匹配.

綜上所述，對?e′∈E(G×Pl)，G×Pl-e′中任意一條邊都屬于某個完美匹配，即該圖的每一條邊都是可去邊.

注根據(jù)E(1,1)的定義，定理2 可以敘述為：對于任一有完美匹配的連通圖G（δ(G)≥2）和包含l個頂點的路Pl（l≥4），它們的笛卡兒乘積圖G×Pl是E(1,1)的.