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

（石家庄学院理学院，河北石家庄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）的……