M2-等可覆蓋圖的一個(gè)注記

張玉琴，姜雪嬌

(天津大學(xué)理學(xué)院，天津 300072)

M2-等可覆蓋圖的一個(gè)注記

張玉琴，姜雪嬌

(天津大學(xué)理學(xué)院，天津 300072)

圖的覆蓋問(wèn)題是圖論研究的一個(gè)主要內(nèi)容.若圖G的每個(gè)極小H-覆蓋都是它的最小H-覆蓋，則稱圖G為H-等可覆蓋的.為刻畫(huà)2M-等可覆蓋圖的特征，采用分類討論的方法，得出2M-等可覆蓋圖的一個(gè)重要結(jié)果：若連通圖G含6圈，則G不是2M-等可覆蓋的.這為2M-等可覆蓋圖的完全刻畫(huà)奠定了有力的基礎(chǔ).

H-覆蓋；H-等可覆蓋圖；圈

圖的覆蓋問(wèn)題是圖論研究的一個(gè)主要內(nèi)容,具有重要的理論意義與實(shí)際意義．H-等可覆蓋圖的刻畫(huà)問(wèn)題起源于對(duì)H-可分解圖，隨機(jī)H-可填充圖及H-等可填充圖見(jiàn)文獻(xiàn)[1-8]的研究．文獻(xiàn)[9]完全刻畫(huà)了P3-等可覆蓋圖的特征，文獻(xiàn)[10]刻畫(huà)了一些特殊的M2-等可覆蓋圖．筆者考慮的圖都是有限且沒(méi)有孤立結(jié)點(diǎn)的簡(jiǎn)單圖．圖G的階數(shù)為V(G)，邊數(shù)為E(G).k個(gè)結(jié)點(diǎn)的圈用Ck表示．設(shè)M是邊集E(G)的一個(gè)子集，如果M中任何2條邊都不相鄰，則稱M是G的一個(gè)匹配.用Mt(t≥1)來(lái)表示t條邊的匹配．設(shè)e∈E(G)，稱G中與e不相鄰的邊數(shù)為e的邊不鄰度．

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

首先給出文中需要的重要定義和已知結(jié)論．

定義1 設(shè)圖H為圖G的一個(gè)子圖，H1,H2,…,Hk為同構(gòu)于H的G的子圖．若G的每條邊至少出現(xiàn)在一個(gè)Hi(i=1,2,…,k )中，則{H1,H2,…,Hk}稱為G的一個(gè)H-覆蓋.

定義2 設(shè)H1,H2,…,Hk為G的一個(gè)H-覆蓋.若對(duì)于任意Hj,j∈{1,2,…,k} ，)?E(Hj)都不是G的一個(gè)覆蓋，則稱{H1,H2,…,Hk}為G的一個(gè)極小覆蓋．

定義3 若不存在少于k個(gè)同構(gòu)于H的子圖可覆蓋G，則稱{H1,H2,…,Hk}為G的最小H-覆蓋．

定義4 若G的每個(gè)極小H-覆蓋都是它的最小H-覆蓋，則稱G為H-等可覆蓋的．

例如，圈C5是一個(gè)M2-等可覆蓋圖．文獻(xiàn)[10]給出M2-等可覆蓋圖的以下結(jié)果．

命題1 含有m條邊，最大度為d的圖G，其最小2M-覆蓋中所用2M數(shù)為

命題2 記e的邊不鄰度為d1(e)，N(e)表示邊e的鄰邊集，c(G)表示G的最小M2-覆蓋中所用的M2數(shù)，c0(e)表示N(e)的最小M2-覆蓋中所用的M2數(shù)．若圖G中存在邊e，使得d1(e)+c0(e)＞c(G)，則G不是M2-等可覆蓋的；若圖G中存在邊e，使得d1(e)+c0(e)=c(G)．且e的鄰邊集N(e)中有2條邊與G?N(e)中某同一條邊不相鄰，則G不是M2-等可覆蓋的．

2 主要結(jié)果

給出如下2個(gè)重要命題．

命題3 非M2-可覆蓋圖可劃分為3類：

(1) G中僅存在1條邊e與其余邊均相鄰，G?e是M2-可覆蓋的；

(2) G中恰存在2條相鄰邊ei和ej分別與其余邊均相鄰，G?ei?ej是M2-可覆蓋的；

(3) G中至少存在3條邊與其余邊均相鄰，即G為星K1,k(k≥3)或K3.

證 明 由可覆蓋圖的定義立刻可得.

顯然，若G不是M2-可覆蓋的，G一定不是M2-等可覆蓋的．

命題4 設(shè)圖F為圖G的一個(gè)M2-可覆蓋子圖，若F不是M2-等可覆蓋的，且G?F是M2-可覆蓋的，則圖G不是M2-等可覆蓋的.

證 明 取F的一個(gè)不是最小覆蓋的極小M2-覆蓋，再任取G?F的一個(gè)M2-覆蓋，它們的并顯然是G的一個(gè)非最小覆蓋的極小M2-覆蓋，由等可覆蓋的定義知，圖G不是M2-等可覆蓋的.

定理1 若連通圖G含6圈，則G不是M2-等可覆蓋的.

證 明 因?qū)6的每條邊e，都有d1(e)=3，c0(e)=1，c(C6)=3，d1(e)+c0(e)＞c(C6).由命題2，圈C6不是M2-等可覆蓋的.

情形1 GC?中僅存在一條邊e與其余邊均相鄰，即GCe??是2M-可覆蓋的.因?yàn)閑至多與C的4條邊相鄰，即至少有C的2條邊與e不相鄰，不妨設(shè)其中的一條邊為e1.則{{e1,e}，{e1,e3}，{e1,e4}，{e2,e5}，{e2,e6}}是C∪e的一個(gè)極小M2-覆蓋，因?yàn)椋?C∪e的最小M2-覆蓋中所用M2數(shù)為4，所以它不是C∪e的最小M2-覆蓋，從而C∪e不是M2-等可覆蓋的，而G?C?e是M2-可覆蓋的，由命題4，G不是M2-等可覆蓋的．

情形2 G?C中恰存在2條邊ei和ej分別與其余邊均相鄰，即G?C?ei?ej是M2-可覆蓋的．因?yàn)閑i與ej必相鄰，對(duì)于C∪ei∪ej，有以下2種可能．

(1) C中至少存在1條邊(不妨設(shè)為e1)與ei和ej均不相鄰，則{{e1,ei}，{e1,ej}，{e1,e3}，{e1,e4}，{e2,e5}，{e2,e6}}是C∪ei∪ej的一個(gè)不是最小覆蓋的極小M2-覆蓋，故C∪ei∪ej不是M2-等可覆蓋的，因而G不是M2-等可覆蓋的．

(2) C中每條邊都至少與ei和ej之一相鄰．只有圖1所示一種可能．

圖1 情形2(2)示意Fig.1 Illustration of case 2(2)

圖1中{{e2,ei}，{e4,ej}，{e1,e3}，{e2,e5}，{e2,e6}}是C∪ei∪ej的一個(gè)不是最小覆蓋的極小M2-覆蓋，故C∪ei∪ej不是M2-等可覆蓋的，因而G不是M2-等可覆蓋的．

情形 3 G?C為K3因G是連通的，有以下3種可能．

(1) C與K3有1個(gè)公共結(jié)點(diǎn)，則{{e2,ei}，{e4,ej}，{e4,ek}，{e1,e3}，{e2,e5}，{e2,e6}}是圖C∪K3(即圖G)的一個(gè)不是最小覆蓋的極小M2-覆蓋，所以G不是M2-等可覆蓋的．

圖2 情形3(1)示意Fig.2 Illustration of case 3(1)

(2) C與3K有2個(gè)公共結(jié)點(diǎn)，有圖3所示3種可能．

圖3 情形3(2)示意Fig.3 Illustration of case 3(2)

圖3(a)中，{{e2,ei}，{e4,ej}，{e4,e1}，{e1,e3}，{e2,e5}，{e2,e6}}是圖G的一個(gè)不是最小覆蓋的極小M2-覆蓋.

圖3(b)中，{{e2,ei}，{e4,ej}，{e1,e3}，{e2,e5}，{e2,e6}，{e4,ek}}是圖G的一個(gè)不是最小覆蓋的極小M2-覆蓋．

圖3(c)中，{{e2,ei}，{e4,ej}，{e1,e3}，{e2,e5}，{e2,e6}，{e4,ek}}是圖G的一個(gè)不是最小覆蓋的極小M2-覆蓋.

所以G不是M2-等可覆蓋的．

(3) C與K3有3個(gè)公共結(jié)點(diǎn)，只有圖4所示1種可能．

圖4 情形3(3)示意Fig.4 Illustration of case 3(3)

則{{e1,e5}，{e2,ei}， {e3,e5}，{ej,e5}，{e4,e6}，{ek,e6}}是圖C∪K3(即圖G)的一個(gè)不是最小覆蓋極小M2-覆蓋.

情形4 G?C為星K1,k(k≥3).記星K1,k(k≥3)的k條邊分別為e01,e02,…,e0k.因?yàn)镚是連通的，有2種可能．

(1) 星的中心是C的一個(gè)結(jié)點(diǎn)(不妨設(shè)為v1).又有如下4種可能：

① 星的其余結(jié)點(diǎn)均不在C上.則{{e2,e01}，{e2,e02}，…，{e2,e0k}，{e1,e3}，{e1,e4}，{e2,e5}，{e2,e6}}是圖G的一個(gè)不是最小覆蓋的極小M2-覆蓋(見(jiàn)圖5).

圖5 情形4(1)①示意Fig.5 Illustration of case 4(1)①

② 星的其余結(jié)點(diǎn)只有1個(gè)結(jié)點(diǎn)v0i在C上，不妨設(shè)v1v0i=e0i.有圖6所示2種可能．

圖6 情形4(1)②示意Fig.6 Illustration of case 4(1)②

無(wú)論哪個(gè)圖中，{{e2,e01}，{e2,e02}，…，{e2,e0i}，…，{e2,e0k}，{e1,e3}，{e1,e4}，{e2,e5}，{e2,e6}} 都是圖G的一個(gè)不是最小覆蓋的極小M2-覆蓋.

③ 星的其余結(jié)點(diǎn)中恰有2個(gè)結(jié)點(diǎn)v0i，v0j在C上，不妨設(shè)v1v0i=e0i，v1v0j=e0j，有圖7所示2種可能．

圖7 情形4(1)③示意Fig.7 Illustration of case 4(1)③

圖7(a)中，{{e2,e01}，{e2,e02}，…，{e2,e0i}，…，{e2,e0k}，{e1,e3}，{e1,e4}，{e2,e5}，{e2,e6}}是圖G的一個(gè)非最小覆蓋的極小M2-覆蓋.

圖7(b)中，{{e3,e01}，{e3,e02}，…，{e3,e0i?1}，{e4,ei}，{e3,e0i+1}，…，{e3,e0k}，{e5,e3}，{e6,e3}，{e1,e4}，{e2,e4}}是圖G的一個(gè)非最小覆蓋的極小M2-覆蓋.

④ 星的其余結(jié)點(diǎn)恰有3個(gè)在C上.只有圖8所示1種可能．

圖8 情形4(1) ④示意Fig.8 Illustration of case 4(1)④

這時(shí)，存在邊e3，使得d1(e3)=k+6?4?1=k +1，c0(e3)=2，c(G)=k+2，d1(e3)+c0(e3)＞c(G)，由命題2，G不是M2-等可覆蓋的.

所以，在(1)下，G都不是M2-等可覆蓋的.

(2) 星的中心在C的結(jié)點(diǎn)外.因?yàn)镚是連通的，有6種可能.

① 星的其余結(jié)點(diǎn)中只有1個(gè)結(jié)點(diǎn)在C上，如圖9所示．

圖9 情形4(2)①示意Fig.9 Illustration of case 4(2)①

則存在邊e2，使得d1(e2)=k+6?3=k+3，

② 星的其余結(jié)點(diǎn)中恰有2個(gè)結(jié)點(diǎn)在C上，有圖10所示3種可能．

圖10 情形4(2)②示意Fig.10 Illustration of case 4(2)②

圖10中都存在邊e5，使得d1(e5)=k+6?3=

③ 星的其余結(jié)點(diǎn)中恰有3個(gè)結(jié)點(diǎn)在C上，有圖11所示3種可能．

在圖11(a)(b)中，存在邊e5，d1(e5)=k+6?3=邊e2，d1(e2)=k+6?3?1=k+2，c0(e2)=2,Δ(G) =k，

④ 星的其余結(jié)點(diǎn)中恰有4個(gè)結(jié)點(diǎn)在C上，有圖12所示3種可能．

圖11 情形4(2)③示意Fig.11 Illustration of case 4(2)③

圖12 情形4(2)④示意Fig.12 Illustration of case 4(2)④

都存在邊5e，使得

⑤ 星的其余結(jié)點(diǎn)中恰有5個(gè)結(jié)點(diǎn)在C上，只有圖13所示1種可能．

則存在邊e5，使得d1(e5)=k+6?3?1=k+2，

圖13 情形4(2)⑤示意Fig.13 Illustration of case 4(2)⑤

⑥ 星的其余結(jié)點(diǎn)中恰有6個(gè)結(jié)點(diǎn)在C上，只有圖14所示1種可能．

圖14 情形4(2)⑥示意Fig.14 Illustration of case 4(2)⑥

則對(duì)邊e5，有d1(e5)=k+6?4?1=k+1，c0(e5)=

所以，在情形4的(2)下，由命題2，G都不是M2-等可覆蓋的．

綜上，若G含6圈，則G不是M2-等可覆蓋的．

類似可得：

定理2 若連通圖G含7圈，則G不是2M-等可覆蓋的.

3 結(jié) 語(yǔ)

定理1和定理2的得出，為2-M等可覆蓋圖的完全刻畫(huà)奠定了有力的基礎(chǔ).

［1］ Ruiz S. Randomly decomposable graphs[J]. Discrete Mathematics，1985，57(1/2)：123-128.

［2］ Beineke L W，Hamberger P，Goddard W D. Random packings of graphs[J]. Discrete Mathematics，1994，125 (1/2/3)：45-54.

［3］ Hartnell B L，Vestergaard P D. Equipackable graphs[J]. Bull Inst Combin Apl，2006，46：35-48.

［4］ Vestergaard P D. A short update on equipackable graphs [J]. Discrete Mathematics，2008，308(2/3)：161-165.

［5］ Zhang Yuqin，F(xiàn)an Yonghui.2M-equipackable graphs[J]. Discrete Applied Mathematics，2006，154(12)：1766-1770.

［6］ Zhang Yuqin.3P-equicoverable graphs：Reasearch on H-equicoverable graphs[J]. Discrete Applied Mathematics，2008，156(5)：647-661.

［7］ Molina R，McNally M，Smith K. Characterizing randomly Pk-decomposable graph for k≤9[J]. Congressus Numerantium，2002，156：211-221.

［8］ Bialostocki A，Roditty Y. 3K2-docomposition of a graph [J]. Acta Math Hunger，1982，40：201-208.

［9］ Zhang Yuqin. P3-equicoverable graphs：Reasearch on H-equicoverable graphs[J]. Discrete Applied Mathematics，2008，156(5)：647-661.

［10］ 張玉琴，蘭文華. 幾類特殊的M2-等可覆蓋圖[J]. 天津大學(xué)學(xué)報(bào)，2009，42(1)：83-85.

Zhang Yuqin，Lan Wenhua. Some special2-Mequicoverable graphs[J]. Journal of Tianjin University，2009，42(1)：83-85(in Chinese).

Note on M2-Equicoverable Graphs

ZHANG Yu-qin，JIANG Xue-jiao
(School of Sciences，Tianjin University，Tianjin 300072，China)

Covering of graphs is a main content of graph theory. A graph G is called H-equicoverable if every minimal H-covering in G is also a minimum H-covering in G. To give the characterization of M2-equicoverable graphs，an important result for connected M2-equicoverable graphs is obtained by using the method of case by case：if Gis a connected graph that contains a 6-cycle，then G is not M2-equicoverable. This result provides a strong base for entirely characterizing all M2-equicoverable graphs.

H-covering；H-equicoverable graph；cycle

O157.5

A

0493-2137(2011)05-0466-05

2010-03-01；

2010-06-04.

國(guó)家自然科學(xué)基金資助項(xiàng)目（10926071，10701033）.

張玉琴（1974— ），女，博士，副教授.

張玉琴，yuqinzhang@126.com.