廣義Halin圖的競爭數(shù)

曹志軍，趙永強(qiáng)，葉國妍，崔永剛

（石家莊學(xué)院理學(xué)院，河北石家莊050035）

廣義Halin圖的競爭數(shù)

曹志軍，趙永強(qiáng)，葉國妍，崔永剛

（石家莊學(xué)院理學(xué)院，河北石家莊050035）

對(duì)于任意圖G，G并上足夠多的孤立頂點(diǎn)就為某個(gè)無圈有向圖的競爭圖.這樣加進(jìn)來的孤立頂點(diǎn)的最少個(gè)數(shù)稱為圖G的競爭數(shù)，記作k（G）.一般來說計(jì)算圖的競爭數(shù)是比較困難的，并且通過計(jì)算圖的競爭數(shù)來刻畫圖已成為研究競爭圖理論的一個(gè)重要內(nèi)容.廣義Halin圖包括一個(gè)樹的平面嵌入和一個(gè)連接樹的葉子的圈.針對(duì)廣義Halin圖進(jìn)行研究，確定了廣義Halin圖的競爭數(shù).

競爭圖；競爭數(shù)；邊團(tuán)覆蓋數(shù)；Halin圖；廣義Halin圖

1 問題提出

競爭圖概念是由著名生物學(xué)家Cohen[1]在研究生態(tài)學(xué)問題時(shí)提出的.設(shè)D=（V，A）為一個(gè)有向圖，其中V為頂點(diǎn)集，A為有向邊集.D的競爭圖C（D）為無向簡單圖，其頂點(diǎn)集與D的頂點(diǎn)集相同，對(duì)任意x，y∈V，xy為C（D）的一條邊的充要條件為：存在頂點(diǎn)v∈V，使得xv，yv∈A.對(duì)于無向圖G，如果存在有向圖D使得C（D）=G，則稱G為競爭圖.

Roberts[2]指出，對(duì)于任意無向圖G，G并上足夠多的孤立頂點(diǎn)就是某個(gè)無圈有向圖的競爭圖.這樣加進(jìn)來的孤立頂點(diǎn)的最少個(gè)數(shù)稱為圖G的競爭數(shù)，記作k（G）.計(jì)算圖的競爭數(shù)是很困難的，正如Opsut[3]指出，計(jì)算圖的競爭數(shù)是一個(gè)NP-hard問題.但是通過計(jì)算圖的競爭數(shù)來刻畫圖已成為研究競爭圖理論的一個(gè)重要內(nèi)容.近年來，人們?cè)诟偁帞?shù)的計(jì)算方面做了大量工作，詳見文獻(xiàn)[4-8].

用Ir表示r個(gè)孤立頂點(diǎn)構(gòu)成的集合，G∪Ir表示向圖G中加r個(gè)孤立頂點(diǎn)構(gòu)成的圖.設(shè)S是圖G的頂點(diǎn)集V（G）的一個(gè)子集，導(dǎo)出子圖G[S]是G的一個(gè)子圖，其頂點(diǎn)集為S，邊集為由G的兩個(gè)端點(diǎn)都在S的邊構(gòu)成.

本研究所涉及的圖都是連通簡單圖.對(duì)于圖G的任意頂點(diǎn)v，G的與v相鄰的頂點(diǎn)稱為v的鄰居，v的全部鄰居構(gòu)成的集合稱為v的鄰域，記作NG（v）.對(duì)于圖G的頂點(diǎn)集的任一子集S，G的與S中頂點(diǎn)相鄰的頂點(diǎn)構(gòu)成的集合稱為S的鄰域，記作NG（S）.圖G的頂點(diǎn)集的子集S稱為G的團(tuán)，如果G[S]為完全圖.對(duì)于圖G的一個(gè)團(tuán)S和G的一條邊e，如果e的兩個(gè)端點(diǎn)都屬于S，則e稱S被覆蓋.圖G的邊團(tuán)覆蓋是指G的一族團(tuán)，使得G的每條邊都被這族團(tuán)中的某個(gè)團(tuán)覆蓋，圖G的邊團(tuán)覆蓋的最小數(shù)目稱為G的邊團(tuán)覆蓋數(shù)，記為θe（G）.圖G的頂點(diǎn)團(tuán)覆蓋是指G的一族團(tuán)，使得G的每個(gè)頂點(diǎn)都屬于這族團(tuán)中的某個(gè)團(tuán)，圖G的頂點(diǎn)團(tuán)覆蓋的最小數(shù)目稱為G的頂點(diǎn)團(tuán)覆蓋數(shù)，記為θv（G）.

廣義Halin圖G=T∪C為平面圖，包含樹T的平面嵌入以及連接T的葉子（度為1的頂點(diǎn)）的圈C，并且C為外部面的邊界.分別稱樹T和圈C為圖G的特征樹和伴隨圈.

當(dāng)廣義Halin圖G的每個(gè)頂點(diǎn)的度都大于等于3時(shí)，G為Halin圖.

對(duì)廣義Halin圖進(jìn)行研究，通過構(gòu)造有向圖得到了廣義Halin圖的競爭數(shù)的取值上界，通過計(jì)算邊團(tuán)覆蓋數(shù)得到廣義Halin圖的競爭數(shù)的取值下屆，進(jìn)而得到其準(zhǔn)確值.

2 主要結(jié)果

關(guān)于圖的競爭數(shù)的下界，Opsut[3]給出了如下兩個(gè)結(jié)果.

定理1[3]對(duì)于任何圖G，k（G）≥θe（G）-｜V（G）｜+2.

定理2[3]對(duì)于任何圖G，k（G）≥min{θv（NG（v））｜v∈V（G）}.

現(xiàn)在考慮廣義Halin圖的競爭數(shù)的上界.先介紹兩個(gè)非常有用的引理.

引理3[9]令D=（V，A）為一個(gè)具有n個(gè)頂點(diǎn)的有向圖.則D無圈的充要條件為：存在頂點(diǎn)的一個(gè)排序σ=[v1，v2，…，vn]，使得下面兩個(gè)條件之一必成立，1）對(duì)于任意i，j∈{1,2，…，n}，若{vi，vj}∈A，則i＜j；2）對(duì)于任意i，j∈{1,2，…，n}，若{vi，vj}∈A，則i＞j.

由此引理可知，如果D是一個(gè)無圈有向圖，則存在一個(gè)頂點(diǎn)標(biāo)號(hào)：

σ∶D→{1,2，…，｜V｜}，

使得當(dāng){x，y}∈A時(shí)，都有σ（x）＜σ（y）[或都有σ（x）＞σ（y）].稱σ為D的無圈標(biāo)號(hào).反過來，如果D是一個(gè)具有無圈標(biāo)號(hào)的有向圖，則D是無圈的.

引理4[10]對(duì)于具有n個(gè)頂點(diǎn)的樹T及其一個(gè)頂點(diǎn)v，存在無圈有向圖D，使得T∪（v0）是D的競爭圖，并且頂點(diǎn)v在D中只有出弧，其中v0為不屬于T的孤立頂點(diǎn).

Kim等[10]用如下算法證明了這個(gè)引理.

令T1=T，V（D1）=V（T），A（D1）=?.從T1中選一個(gè)度為1的頂點(diǎn)v1，如果v1是T1中與v1相鄰的頂點(diǎn)，令T2=T1-v1，V（D2）=V（D1）∪（v0），A（D2）={（v1，v0），（v1，v0）}，其中v0是不屬于T的孤立頂點(diǎn).假設(shè)已經(jīng)得到了Ti和Di，從Ti中選取一個(gè)度為1的頂點(diǎn)vi，如果vi是Ti中與vi相鄰的頂點(diǎn)，則令Ti+1=Ti-vi，V（Di+1）=V（Di），A（Di+1）=A（Di）∪{（vi，vi-1），（vi，vi-1）}.重復(fù)上面的步驟直到Dn被確定.令D=（V（Dn），A（Dn））.在這個(gè)過程中，可以最后選取頂點(diǎn)v，因?yàn)樵陧旤c(diǎn)個(gè)數(shù)至少為2的樹中，1度頂點(diǎn)至少有兩個(gè)，所以這一點(diǎn)總可以做到.

事實(shí)上，這個(gè)算法給出了D的頂點(diǎn)的一個(gè)無圈標(biāo)號(hào)σ=[v0，v1，v2，…，vn]，使得vn=vn-1，vn-1vn∈E（T），并且vn-1和vn在D中都只有出弧.

任取v∈V（C），如果對(duì)于任意x∈NC（v），都有NT（v）∩NT（x）=?，則稱v為T的單葉，否則稱v為T的復(fù)葉.分別用V1和V2表示T的全部單葉和全部復(fù)葉構(gòu)成的集合.顯然V（C）=V1∪V2，并且V1∩V2=?.令V1′=NT（V1），V2′=NT（V2）.

引理5對(duì)于任何非K4廣義Halin圖G，

證明令G=T∪C為一個(gè)非K4廣義Halin圖，這里T和C和分別是G的特征樹和伴隨圈.沿著圈C的順時(shí)針方向把V（2如果V2≠?）劃分成r（≥1）個(gè)子集為C在T上的連續(xù)復(fù)葉的極大子集，并且中的所有頂點(diǎn)有一個(gè)公共的鄰居.令中點(diǎn)的公共鄰居，其中1≤i≤r.假設(shè)的頂點(diǎn)沿順時(shí)針方向依次為，這里αi≥2，1≤i≤r.把圈C上介于之間的所有頂點(diǎn)構(gòu)成的集合記為且在V（C）中任意選取一個(gè)頂點(diǎn)作為

根據(jù)引理3以及引理4的證明中所用算法，對(duì)于不屬于樹T中的頂點(diǎn)v0，可以構(gòu)造一個(gè)無圈有向圖D，使得T∪{v0}為D的競爭圖，并且得到D的一個(gè)無圈標(biāo)號(hào)：

使得：

如果V1≠?，V2≠?，則

所以結(jié)論成立.

引理6對(duì)于任何非K4廣義Halin圖

證明令G=T∪C為一個(gè)非K4廣義Halin圖，這里T和C分別是圖G的特征樹和伴隨圈.因?yàn)閷?dǎo)出子圖G[V（G）V（C）]是樹，所以：

另外容易驗(yàn)證導(dǎo)出子圖G[V1∪V1′]的邊團(tuán)覆蓋數(shù)θe（G[V1∪V1′]）=｜V1｜.

不難看出3個(gè)子圖G[V（G）V（C）]、G[V（C）∪V2′]和G[V1∪V1′]中的任意兩個(gè)都沒有公共邊，所以有：

即

定理7對(duì)于任意廣義Halin圖G，

證明情形1：G=K4.結(jié)論顯然成立.

情形2：G≠K4并且V1=?.

因?yàn)閷?duì)于每個(gè)頂點(diǎn)v∈V（G），都有θv[NG（v）]≥2，由定理2可知：

另一方面，根據(jù)引理5的情形1可知k（G）≤2.所以有k（G）=2.

情形3：G≠K4并且V1≠?.

由定理1、引理5和引理6結(jié)果得證.

3 結(jié)束語

研究了廣義Halin圖的競爭數(shù)，得到了任意廣義Halin圖的競爭數(shù)的準(zhǔn)確值.因?yàn)楫?dāng)廣義Halin圖的每個(gè)頂點(diǎn)的度都大于等于3時(shí)，為Halin圖，所以本研究主要結(jié)果對(duì)Halin圖也成立.

[1]COHENJE.IntervalGraphsandFoodWebs:AFindingandaProblem[R].SantaMonica,CA:RandCorporation Document17696-PR, 1968.

[2]ROBERTSFS.FoodWebs,CompetitionGraphs,andtheBoxicityofEcologicalPhaseSpace[M].NewYork:SpringerBerlinHeidelberg, 1978:477-490.

[3]OPSUT R J.On the Computation of the Competition Number of a Graph[J].SIAM Journal on Algebraic Discrete Methods,2006,3（3）: 420-428.

[4]KAMIBEPPUA.AnUpperBoundfortheCompetitionNumbersofGraphs[J].DiscreteAppliedMathematics,2010,158（2）:154-157.

[5]KIMSR,PARKB,SANOY.TheCompetitionNumbersofJohnsonGraphs[J].DiscussionesMathematicaeGraphTheory,2010,30（3）：449-459.

[6]LEEJY,KIMSR,KIMSJ,etal.TheCompetitionNumberofaGraphwithExactlyTwoHoles[J].ArsCombinatoria,2010,95:45-54.

[7]KIMSR,LEEJY,PARKB,etal.TheCompetitionNumberofaGraphandtheDimensionofItsHoleSpace[J].AppliedMathematicsLetters,2012,25(3):638-642.

[8]KUHLJ.Transversalsand Competition Numbers of Complete Multipartite Graphs[J].Discrete Applied Mathematics,2013,161(3):435-440.

[9]HARARYF,NORMANRZ,CARTWRIGHTD.StructureModels:AnIntroductiontotheTheoryofDirectedGraphs[M].NewYork:Wiley,1965.

[10]KIMSR,ROBERTSFS.CompetitionNumbersofGraphswithaSmallNumberofTriangles[J].DiscreteAppliedMathematics,1997,78 (1-3):153-162.

（責(zé)任編輯鈕效鹍）

Competition Numbers of Generalized Halin Graphs

CAO Zhi-jun,ZHAO Yong-qiang,YE Guo-yan,CUI Yong-gang
(School of Science,Shijiazhuang University,Shijiazhuang,Hebei 050035,China)

For any graph G,G together with sufficiently many isolated vertices is the competition graph of some acyclic digraph.The competition number k(G)of a graph G is defined to be the smallest number of such isolated vertices.In general,it is hard to compute the competition number k(G)for a graph G and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs.A generalized Halin graph is a planar graph consisting of a tree and a cycle connecting the leaves of the tree.This paper computes the competition numbers of generalized Halin graphs.

competition graph;competition number;edge clique cover;Halin graph;generalized Halin graph

O157.5

A

1673-1972（2017）03-0073-04

2017-04-05

河北省自然科學(xué)基金（A2015106045）

曹志軍（1975-），男，河北邢臺(tái)人，講師，主要從事圖論及其應(yīng)用研究.