广义Halin图的竞争数

曹志军，赵永强，叶国妍，崔永刚

（石家庄学院理学院，河北石家庄050035）

广义Halin图的竞争数

曹志军，赵永强，叶国妍，崔永刚

（石家庄学院理学院，河北石家庄050035）

对于任意图G，G并上足够多的孤立顶点就为某个无圈有向图的竞争图.这样加进来的孤立顶点的最少个数称为图G的竞争数，记作k（G）.一般来说计算图的竞争数是比较困难的，并且通过计算图的竞争数来刻画图已成为研究竞争图理论的一个重要内容.广义Halin图包括一个树的平面嵌入和一个连接树的叶子的圈.针对广义Halin图进行研究，确定了广义Halin图的竞争数.

竞争图；竞争数；边团覆盖数；Halin图；广义Halin图

1 问题提出

竞争图概念是由著名生物学家Cohen[1]在研究生态学问题时提出的.设D=（V，A）为一个有向图，其中V为顶点集，A为有向边集.D的竞争图C（D）为无向简单图，其顶点集与D的顶点集相同，对任意x，y∈V，xy为C（D）的一条边的充要条件为：存在顶点v∈V，使得xv，yv∈A.对于无向图G，如果存在有向图D使得C（D）=G，则称G为竞争图.

Roberts[2]指出，对于任意无向图G，G并上足够多的孤立顶点就是某个无圈有向图的竞争图.这样加进来的孤立顶点的最少个数称为图G的竞争数，记作k（G）.计算图的竞争数是很困难的，正如Opsut[3]指出，计算图的竞争数是一个NP-hard问题.但是通过计算图的竞争数来刻画图已成为研究竞争图理论的一个重要内容.近年来，人们在竞争数的计算方面做了大量工作，详见文献[4-8].

用Ir表示r个孤立顶点构成的集合，G∪Ir表示向图G中加r个孤立顶点构成的图.设S是图G的顶点集V（G）的一个子集，导出子图G[S]是G的一个子图，其顶点集为S，边集为由G的两个端点都在S的边构成.

本研究所涉及的图都是连通简单图.对于图G的任意顶点v，G的与v相邻的顶点称为v的邻居，v的全部邻居构成的集合称为v的邻域，记作NG（v）.对于图G的顶点集的任一子集S，G的与S中顶点相邻的顶点构成的集合称为S的邻域，记作NG（S）.图G的顶点集的子集S称为G的团，如果G[S]为完全图.对于图G的一个团S和G的一条边e，如果e的两个端点都属于S，则e称S被覆盖.图G的边团覆盖是指G的一族团，使得G的每条边都被这族团中的某个团覆盖，图G的边团覆盖的最小数目称为G的边团覆盖数，记为θe（G）.图G的顶点团覆盖是指G的一族团，使得G的每个顶点都属于这族团中的某个团，图G的顶点团覆盖的最小数目称为G的顶点团覆盖数，记为θv（G）.

广义Halin图G=T∪C为平面图，包含树T的平面嵌入以及连接T的叶子（度为1的顶点）的圈C，并且C为外部面的边界.分别称树T和圈C为图G的特征树和伴随圈.

当广义Halin图G的每个顶点的度都大于等于3时，G为Halin图.

对广义Halin图进行研究，通过构造有向图得到了广义Halin图的竞争数的取值上界，通过计算边团覆盖数得到广义Halin图的竞争数的取值下届，进而得到其准确值.

2 主要结果

关于图的竞争数的下界，Opsut[3]给出了如下两个结果.

定理1[3]对于任何图G，k（G）≥θe（G）-｜V（G）｜+2.

定理2[3]对于任何图G，k（G）≥min{θv（NG（v））｜v∈V（G）}.

现在考虑广义Halin图的竞争数的上界.先介绍两个非常有用的引理.

引理3[9]令D=（V，A）为一个具有n个顶点的有向图.则D无圈的充要条件为：存在顶点的一个排序σ=[v1，v2，…，vn]，使得下面两个条件之一必成立，1）对于任意i，j∈{1,2，…，n}，若{vi，vj}∈A，则i＜j；2）对于任意i，j∈{1,2，…，n}，若{vi，vj}∈A，则i＞j.

由此引理可知，如果D是一个无圈有向图，则存在一个顶点标号：

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

使得当{x，y}∈A时，都有σ（x）＜σ（y）[或都有σ（x）＞σ（y）].称σ为D的无圈标号.反过来，如果D是一个具有无圈标号的有向图，则D是无圈的.

引理4[10]对于具有n个顶点的树T及其一个顶点v，存在无圈有向图D，使得T∪（v0）是D的竞争图，并且顶点v在D中只有出弧，其中v0为不属于T的孤立顶点.

Kim等[10]用如下算法证明了这个引理.

令T1=T，V（D1）=V（T），A（D1）=Ø.从T1中选一个度为1的顶点v1，如果v1是T1中与v1相邻的顶点，令T2=T1-v1，V（D2）=V（D1）∪（v0），A（D2）={（v1，v0），（v1，v0）}，其中v0是不属于T的孤立顶点.假设已经得到了Ti和Di，从Ti中选取一个度为1的顶点vi，如果vi是Ti中与vi相邻的顶点，则令Ti+1=Ti-vi，V（Di+1）=V（Di），A（Di+1）=A（Di）∪{（vi，vi-1），（vi，vi-1）}.重复上面的步骤直到Dn被确定.令D=（V（Dn），A（Dn））.在这个过程中，可以最后选取顶点v，因为在顶点个数至少为2的树中，1度顶点至少有两个，所以这一点总可以做到.

事实上，这个算法给出了D的顶点的一个无圈标号σ=[v0，v1，v2，…，vn]，使得vn=vn-1，vn-1vn∈E（T），并且vn-1和vn在D中都只有出弧.

任取v∈V（C），如果对于任意x∈NC（v），都有NT（v）∩NT（x）=Ø，则称v为T的单叶，否则称v为T的复叶.分别用V1和V2表示T的全部单叶和全部复叶构成的集合.显然V（C）=V1∪V2，并且V1∩V2=Ø.令V1′=NT（V1），V2′=NT（V2）.

引理5对于任何非K4广义Halin图G，

证明令G=T∪C为一个非K4广义Halin图，这里T和C和分别是G的特征树和伴随圈.沿着圈C的顺时针方向把V（2如果V2≠Ø）划分成r（≥1）个子集为C在T上的连续复叶的极大子集，并且中的所有顶点有一个公共的邻居.令中点的公共邻居，其中1≤i≤r.假设的顶点沿顺时针方向依次为，这里αi≥2，1≤i≤r.把圈C上介于之间的所有顶点构成的集合记为且在V（C）中任意选取一个顶点作为

根据引理3以及引理4的证明中所用算法，对于不属于树T中的顶点v0，可以构造一个无圈有向图D，使得T∪{v0}为D的竞争图，并且得到D的一个无圈标号：

使得：

如果V1≠Ø，V2≠Ø，则

所以结论成立.

引理6对于任何非K4广义Halin图

证明令G=T∪C为一个非K4广义Halin图，这里T和C分别是图G的特征树和伴随圈.因为导出子图G[V（G）V（C）]是树，所以：

另外容易验证导出子图G[V1∪V1′]的边团覆盖数θe（G[V1∪V1′]）=｜V1｜.

不难看出3个子图G[V（G）V（C）]、G[V（C）∪V2′]和G[V1∪V1′]中的任意两个都没有公共边，所以有：

即

定理7对于任意广义Halin图G，

证明情形1：G=K4.结论显然成立.

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

因为对于每个顶点v∈V（G），都有θv[NG（v）]≥2，由定理2可知：

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

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

由定理1、引理5和引理6结果得证.

3 结束语

研究了广义Halin图的竞争数，得到了任意广义Halin图的竞争数的准确值.因为当广义Halin图的每个顶点的度都大于等于3时，为Halin图，所以本研究主要结果对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.

（责任编辑钮效鹍）

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

河北省自然科学基金（A2015106045）

曹志军（1975-），男，河北邢台人，讲师，主要从事图论及其应用研究.