圖的導出匹配覆蓋.pdf

1、本文所討論的圖均為有限的簡單圖.對于任意圖G，V(G)和E(G)分別表示它的頂點集和邊集.對頂點集X∈V(G)，令EG(X)={uv∈E(G)：u，v∈X}.X的鄰點集NG(X)定義為NG(X)={y∈V(G)\X：存在x∈X使得xy∈E(G)}.X的懸掛鄰集N0(X)定義為N0(X)={y∈NG(X)：d(y)=1}.對任意頂點v，v的懸掛度定義為d0(v)=|N0(v)|.對于M∈E(G)，令V(M)={v∈V(G)：存在一個頂點x

2、∈V(G)使得vs∈M}.如果M∈E(G)，X()V(G)使得X()V(M)，我們稱M覆蓋X.如果M()E(G)，且對任意不同的邊e，f∈M，V(e)∩V(f)=Φ，則稱M是圖G的一個匹配.若匹配M滿足V(M)=V(G)，則稱M是圖G的完美匹配.若匹配M滿足EG(V(M))=M，則稱M是圖G的導出匹配. 集合X的一個k-劃分是指一個k-元組(X1，X2，…，Xk)使得X1，X2，…，Xk是滿足∪Xi=X的X的互不相交的子集.如果

3、G是有完美匹配的連通圖，假設(V1，V2，…，Vk)是V(G)的一個k-劃分.我們說(V1，V2，…，Vk)是G的一個k-導出匹配劃分，如果對每一個i(1≤i≤k)而言，G[Vi]是G的一個1-正則導出子圖.G的導出匹配劃分數(shù)定義為使得G有k-導出匹配劃分的最小整數(shù)k，記為imp(G). 設M1，M2，…，Mk是G的k個導出匹配，若V(M1)∪…∪V(Mk)=V(G)，則稱{M1，M2，…，Mk}是G的一個k-導出匹配覆蓋.G的

4、導出匹配覆蓋數(shù)定義為使得G有k-導出匹配覆蓋的最小整數(shù)k，記為imc(G). 如果G是頂點數(shù)至少為3的樹.我們記△0(G)=max{d0(u)：u∈V(G)}，△*0(G)=max{d0(u)+d0(v)：u，v∈V(G)，uv∈E(G)}.在本文中，我們主要研究了以下兩個部分：(1)樹和3-正則無爪圖的導出匹配覆蓋；(2)圖的導出匹配覆蓋問題的計算復雜性. 第二章討論了樹和3-正則無爪圖的導出匹配覆蓋，主要得到以下結果

5、：定理1設G是頂點數(shù)至少為3的樹.則imc(G)∈{*0(G)，△*0(G)+1，△*0(G)+2}，其中△*0(G)=max{d0(u)+d0(v)：u，v∈V(G)，uv∈E(G)}.進一步，如果△*0(G)＞△0(G)，則imc(G)∈{△*0(G)，△*0(G)+1}.定理2設G是3-正則無爪圖，則imc(G)∈{2，3}. 第三章研究了圖的導出匹配覆蓋問題的計算復雜性，主要結果如下：定理3直徑為6的圖的2-導出匹配覆蓋

6、問題是NP-完備的.定理4直徑為2的圖的3-導出匹配覆蓋問題是NP-完備的.定理5設G是直徑為2的圖.令X={x∈V(G)：dG(x)=2}.則imc(G)=2當且僅當下列兩個條件之一成立：(1)imp(G)=2；(2)imp(G)≠2，且存在這樣的頂點x∈X使得(G-{x})∪K+E0，記為G1，滿足imp(G1)=2，其中K是空圖，|V(K)|=2，K∩V(G)=Φ，E0={(y，z)：y∈NG(x)，z∈K}. 最后還給出