一些簡(jiǎn)單有限連通圖的連通包數(shù)

馬儇龍，金劍行，鐘 國(guó)

(廣西師范學(xué)院 數(shù)學(xué)科學(xué)學(xué)院，廣西 南寧530023)

本文中所考慮的圖均是簡(jiǎn)單有限的連通圖，即沒有環(huán)和重邊的無向有限連通圖。對(duì)于一個(gè)有限集合S，通常用|S|表示S中元素的個(gè)數(shù)。設(shè)G=(V，E)是一個(gè)圖，這里V和E分別表示這個(gè)圖G的頂點(diǎn)集和邊集，|V|和|E|分別稱為G的階(order)和大小(size)。如果G中任意兩個(gè)頂點(diǎn)都相連，則這個(gè)圖稱為是完全的。特別地，階為n的完全圖記作Kn。degG(v)表示G中頂點(diǎn)v的度(degree)，當(dāng)上下文不引起混淆時(shí)，可簡(jiǎn)單記為deg(v)。設(shè)S?V，則G［S］表示由點(diǎn)集S誘導(dǎo)的G的子圖。用NG(v)表示G中頂點(diǎn)v的鄰域(neighborhood)，是指與v相鄰接的所有點(diǎn)組成的集合，也可以簡(jiǎn)單記作NG(v)。如果由點(diǎn)v的鄰域NG(v)所誘導(dǎo)的G的子圖是完全的，則稱v是G的一個(gè)極點(diǎn)(extreme－vertex)。對(duì)于連通圖G=(V，E)的頂點(diǎn)c，如果由V{c}誘導(dǎo)G的子圖是不連通的，則稱c是G的一個(gè)割點(diǎn)(cut－vertex)。如果圖G是一條長(zhǎng)(或階)為n的路，則G可記之為Pn;如果圖G是一個(gè)階為n的圈，則可記其為Cn。

圖G中，若頂點(diǎn)u和v之間至少有一條路連接，則G中最短u－v路的長(zhǎng)稱為u和v之間的距離(distance)，且記為d(u，v)。一個(gè)連通圖G的直徑(diameter)是圖中任兩點(diǎn)距離的最大值且被記作diam(G)。一條長(zhǎng)為d(u，v)的u－v路稱為一條u－v測(cè)地線(geodesic)。對(duì)于一個(gè)頂點(diǎn)x，如果x位于某一條u － v測(cè)地線P上，則x被稱為位于u － v測(cè)地線上。對(duì)于兩個(gè)頂點(diǎn)u和v，I［u，v］是所有位于u － v測(cè)地線上的點(diǎn)的集合。對(duì)于V的一個(gè)子集S，則I［S］表示位于集合S中任意兩個(gè)頂點(diǎn)u和v的u －v測(cè)地線上的點(diǎn)的集合之并，即如果對(duì)于任意的集合S(?V)有I［S］= S，則S稱為是一個(gè)凸集(convex set)。若S={v}或S=V，則明顯S是凸的。圖G的凸數(shù)(convexity number)是使得S(?V)是一個(gè)凸集的S的最大的勢(shì)(cardinality，或|S|)，即集合S里面元素的個(gè)數(shù)，并且G的凸數(shù)被記作C(G)。集合S的凸包是指最小的包含S的凸集并且它被記作Ih(S)(由于兩個(gè)凸集的交仍是凸集，故一個(gè)集合的凸包是唯一的，進(jìn)而凸包的定義是合理的)。如果I［S］=V和Ih(S)=V，則S分別稱為G的測(cè)地集(geodetic set)和包集(hull set)，測(cè)地集在文獻(xiàn)［1 －3］中作者已經(jīng)做了充分的研究，而包集在文獻(xiàn)［2 －4］中作者也做了許多研究。G的測(cè)地?cái)?shù)g(G)是G的所有測(cè)地集勢(shì)的最小值。類似地，G的包數(shù)h(G)是G的所有包集勢(shì)的最小值。

一個(gè)連通圖的連通包數(shù)首次提出是在文獻(xiàn)［5］中，作者研究了一些連通包數(shù)的基本性質(zhì)且提出了一些有待解決的問題。本文是關(guān)于連通包集的進(jìn)一步的研究。對(duì)于有關(guān)圖論的一些常見術(shù)語和定義，請(qǐng)參考文獻(xiàn)［6］。

1 連通包數(shù)的定義

定義1.1 設(shè)G=(V，E)是一個(gè)圖且集合S?V。如果S是一個(gè)包集且使得G的子圖G［S］是連通的，則S稱為G的一個(gè)連通包集。所有連通包集中最小的勢(shì)叫做G的連通包數(shù)且被記作hc(G)。

例1.2 對(duì)于圖1，設(shè)S1={v1，v6}，則d(v1，v6)=3，因此I［S1］={v1，v2，v3，v5，v6}。注意到I［S1］不是凸集(因?yàn)関4?I［S1］，但v4∈I［I［S1］］)。于是這個(gè)圖的頂點(diǎn)集V={v1，v2，v3，v5，v6}是包含S1的最小的凸集，即Ih(S1)=V并且S1是圖G的一個(gè)包集，進(jìn)而h(G)=2。注意到G［S1］是不連通的，因此S1不是G的連通包集.現(xiàn)在考慮S2={v1，v2，v3，v6}，顯然I［S1］={v1，v2，v3，v5，v6}，易知Ih(S2)=V，故S2是G的一個(gè)包集.這時(shí)注意到G［S2］是連通的，于是S2是G的一個(gè)連通包集。更進(jìn)一步，可以證明hc(G)=4。另一方面容易看出S3={v1，v2，v3，v6}也是G的一個(gè)連通包集。

圖1 G=(V，E)

2 一些連通圖的連通包數(shù)

引理2.1 設(shè)G=(V，E)是一個(gè)連通圖且S是V的任意一個(gè)子集，則有S?I［S］?Ih(S)?V。

證明 注意到Ih(S)是一個(gè)凸集且包含S，于是I［Ih(S)］=Ih(S)，當(dāng)然I［S］?I［Ih(S)］=Ih(S)，即I［S］?Ih(S)，引理的其它部分顯然成立。

定理2.2 設(shè)n≥2 且G=(V，E)≌Pn，則hc(G)=n。特別地，V是G的一個(gè)最小連通包集。

證明 設(shè)Pn為路v1v2…vn－1vn，考慮到Pn的連通包集所誘導(dǎo)的子圖是連通的，于是Pn的任何一個(gè)連通包集均是這條路上的一個(gè)截?cái)唷Ｒ虼瞬环良僭O(shè)S={vi，vi+1，…，vj－1，vj}是Pn的一個(gè)連通包集.這里下標(biāo)i，i+1，…，j－1，j對(duì)應(yīng)于自然數(shù)集的一個(gè)截?cái)啵@說明由G［S］是連通的。注意到I［S］=S，進(jìn)而S是凸的，根據(jù)包集的定義可知S=V。這說明Pn的任何一個(gè)連通包集均是Pn的頂點(diǎn)集。故Pn的任何一個(gè)最小連通包集也是Pn的頂點(diǎn)集，即hc(G)=n，定理得證。

證明 設(shè)Cn為圈v1v2…vn－1vnv1，考慮到Cn的連通包集所誘導(dǎo)的子圖是連通的，故Cn的任何一個(gè)連通包集均是這個(gè)圈上的一些連續(xù)鄰接的頂點(diǎn)組成。因此不妨假設(shè)S={vi，vi+1，…，vj－1，vj}是Cn的一個(gè)連通包集，這里下標(biāo)i，i+1，…，j－1，j對(duì)應(yīng)于集合{1，2，…，n－1，n，1，2，…}的一個(gè)截?cái)啵@說明由I［S］是連通的。考慮兩種情況:

定理2.4 設(shè)G(V，E)是一個(gè)階為n的樹，則hc(G)= n。

證明 反證。假設(shè)hc(G)≠n，則hc(G)＜n且G存在一個(gè)最小連通包集S使得| S| ＜| V|。因此I［S］≠S(否則，S是個(gè)凸集，這意味著包含S的最小凸集就是它本身，根據(jù)包集定義可知S = V，這是一個(gè)矛盾。)，即存在x∈V使得x∈I［S］但x?S。故x必位于一條u －v測(cè)地線上，這里u，v∈S。于是d(u，v)≥2，這時(shí)注意到u，v在G［S］中是連通的，不妨設(shè)uw1w2…wiv是G［S］中的使得u，v連通的一條路。既然x?S但x位于一條u － v測(cè)地線上，故又可以設(shè)uo1o2…x…oiv是G［I［S］］中的使得u，v連通的一條路，這說明uw1w2…wivoi…x…o2o1u是圖G的子圖G［I［S］］中的一個(gè)圈，即它也是圖G的一個(gè)圈，注意到G是樹，故G中是不含有圈的，這是一個(gè)矛盾。因此假設(shè)不成立，即hc(G)= n。

定理2.5 設(shè)G(V，E)是一個(gè)完全二部圖Kr，s，則

證明 對(duì)于完全完全二部圖Kr，s，如果r=1 或者s=1，則Kr，s是一個(gè)星圖，也就是說Kr，s為一棵樹。于是根據(jù)定理3.4 可知，hc(G)=r+s。現(xiàn)在設(shè)r≠1 且s≠1，考慮下面的兩種可能情況。

情況1:r=2 或者s=2。不妨假設(shè)r=2。若s=2，則G≌C4且hc(G)=3。否則，圖G如圖2 所示，可以斷言S={u，v，w}是G的一個(gè)連通包集，這是因?yàn)镮［S］=V，即I［S］?Ih(S)=V.顯然G［S］是連通的，故S={u，v，w}是勢(shì)最小的連通包集，也就是說此時(shí)hc(G)=3。

情況2:r≠2 或者s≠2。這種情況下圖G如圖3 所示(圖中頂點(diǎn)集{y1，y2，…，yi}中的每個(gè)頂點(diǎn)均和頂點(diǎn)集{x1，x2，…，xi}中每個(gè)頂點(diǎn)鄰接)，容易看出{u，y1，y2，…，yi，v}和{x1，x2，…，xi，w}是G的兩個(gè)劃分集。在這種情況下我們斷言hc(G)=3。令S={u，v，w}，則I［S］={u，v，w，x1，x2，…，xi}。由于集合{y1，y2，…，yi}中的每一個(gè)點(diǎn)都位于x1－w測(cè)地線上而{y1，y2，…，yi}中的每一個(gè)點(diǎn)都不含在I［S］中，故I［S］不是凸集。進(jìn)一步，由于I［S］?Ih(S)=V，注意到Ih(S)是凸集，故Ih(S)包含x1－w測(cè)地線上的每一個(gè)點(diǎn)，于是不得不有Ih(S)=V。這意味著S={u，v，w}是G的一個(gè)連通包集，另一方面，顯然S又是G的一個(gè)勢(shì)最小的連通包集，因此斷言成立。

圖2 hc(G)=3

圖3 hc(G)=3

圖4 Petersen 圖

定理2.6 設(shè)G(V，E)是Petersen 圖，則hc(G)=5。

證明 設(shè)G(V，E)是Petersen 圖，則G是一個(gè)階為10 的3 －正則立方圖，顯然diam(G)=2，見圖4。明顯對(duì)Petersen 圖有hc(G)≥4。下面就hc(G)的大小問題考慮兩種情況。

情況1:若hc(G)=4，則圖G存在一個(gè)最小的連通包集S使得|S| =4 且G［S］是G的連通子圖。4個(gè)頂點(diǎn)的連通簡(jiǎn)單圖有6 個(gè)(見圖5)。從直觀上看出，Petersen 圖G是不存在C3或C4作為其子圖的，因此G［S］只能同構(gòu)于P4或者星圖K1.3(分別為圖5 里面的前兩個(gè))?，F(xiàn)考慮兩種可能:(1)G［S］≌P4。這時(shí)易知G［I［S］］≌C5，而明顯G［I［S］］的頂點(diǎn)集在V中是凸的，于是I［S］是凸集，即I［S］成了G中包含S的最小凸集，根據(jù)連通包集的定義可知I［S］=V，這是一個(gè)矛盾。(2)G［S］≌K1.3，這時(shí)注意到diam(G)=2 且圖G中任二頂點(diǎn)的距離為2 的路是唯一的，于是I［S］=S，即表明S是凸集，根據(jù)連通包集定義同理可知I［S］=S=V，又一個(gè)矛盾。綜合這兩種可能可知hc(G)≠4。

圖5 階為4 的簡(jiǎn)單連通圖(同構(gòu)意義下只有6 個(gè))

情況2:考慮hc(G)≥5。令S={u1，u2，u3，u4，u5}(對(duì)應(yīng)于圖4 中的頂點(diǎn)標(biāo)號(hào))。則I［S］={u1，u2，u3，u4，u5，v1，v2，v5}，由于v4位于v1－v5測(cè)地線上而v4?I［S］，因此I［I［S］］≠I［S］，即I［S］不是凸集。根據(jù)引理2.1 知I［S］?Ih(S)，考慮下面兩種可能。(1)Ih(S)={u1，u2，u3，u4，u5，v1，v2，v3，v5}。如果這樣，則由于v4位于v1－v3測(cè)地線上但v4?Ih［S］，故與Ih(S)的凸性矛盾。(2)Ih(S)={u1，u2，u3，u4，u5，v1，v2，v4，v5}。如果這樣，則由于v3位于v2－v4測(cè)地線上但v3?Ih［S］，故也與Ih(S)的凸性矛盾。故這兩種可能都不成立，于是Ih(S)=V，而這恰恰說明S是G的一個(gè)包集且是連通包集，由證明過程可以斷定S是G的一個(gè)最小連通包集，即hc(G)=5，定理得證。

定理2.7 設(shè)G=(V，E)是一個(gè)輪圖W1，r，見圖6。則

證明 若r =1，則G≌K2，則hc(G)=2;若r =2，則G≌K3，則hc(G)=3;若r =3，則G≌K4，則hc(G)=4。

圖6 輪圖W1，r

圖7 蛛網(wǎng)圖S1，r

定理2.8 設(shè)G(V，E)是一個(gè)蛛網(wǎng)圖S1，r，見圖7，則hc(G)=r+3。

證明 設(shè)G(V，E)是如圖7 所示的蛛網(wǎng)圖S1，r且S是G的一個(gè)最小連通包集。顯然v是圖G的一個(gè)極點(diǎn)，因此$vin S$?，F(xiàn)在通過下面四步完成證明。

步驟1 斷言:vr1，vr2，vr3這三個(gè)頂點(diǎn)中必有一個(gè)屬于集合S。若否，則vr1，vr2，vr3這三個(gè)頂點(diǎn)都不屬于集合S。令T=V{vr1，vr2，vr3}，則明顯I［T］=T，即T是凸集，這表明S?I［S］?Ih(S)?T?V，這與S的定義矛盾。

步驟2 斷言:|S|≥r+2。根據(jù)步驟1，不妨假設(shè)vr1∈S，則頂點(diǎn)v和vr1在子圖G［S］中至少有一條路，注意到diamG(v，vr1)=r，于是|S|≥r+1。若斷言不成立，則|S| =r+1，這時(shí)不得不有S={v，v11，v21，…，vr1}，故有I［S］=S，這是一個(gè)矛盾。

步驟3 斷言:|S|≥r+3。根據(jù)前面兩步的證明可設(shè)v，vr1∈S，如果斷言不成立，則有|S| =r+2，這時(shí)易知I［S］?Ih(S)?{v，v11，v21，…，vr1，v12，v22，…，vr2}?V或者

根據(jù)蛛網(wǎng)圖的一般性質(zhì)可知{v，v11，v21，…，vr1，v12，v22，…，vr2}和{v，v11，v21，…，vr1，v13，v23，…，vr3}均是凸集，這是矛盾。

步驟4 完成證明。步驟3 說明hc(G)≥r+3。另一方面，容易看出集合{v，v11，v21，…，vr1，vr2，vr3}是G的一個(gè)連通包集，這意味著hc(G)=r+3，完成證明。

［1］ Tong L D. The forcing hull and forcing geodetic numbers of graphs［J］. Discrete Applied Math，2009，157:1159 －1163.

［2］ Chartrand G，Harary F，Zhang P. Geodetic Sets in Graphs［J］. Discussiones Mathematicae Graph Theory，2000，(20):129 －138.

［3］ Chartrand G，Zhang P. The forcing geodetic number of a graph［J］. Discuss Math Graph Theory，1999，19:45 －58.

［4］ Evertt M G，Seidman S B. The hull number of a graph［J］. Discrete Math，1985，57:217 －223.

［5］ John J，Mary G V. The connected hull number of a graph［J］. South Asian Journal of Mathematics，2012，2(5):512 －520.

［6］ Chartrand G，Zhang P. Introduction to Graph Theory［M］. Beijing:Posts and Telecom Press，2006.