广义Halin图的竞争数  

Competition Numbers of Generalized Halin Graphs

作　　者：曹志军[1] 赵永强[1] 叶国妍[1] 崔永刚[1] CAO Zhi-jun;ZHAO Yong-qiang;YE Guo-yan;CUI Yong-gang(School of Science, Shijiazhuang University, Shijiazhuang, Hebei 050035, China)

机构地区：[1]石家庄学院理学院,河北石家庄050035

出　　处：《石家庄学院学报》2017年第3期73-76,135,共5页Journal of Shijiazhuang University

基　　金：河北省自然科学基金(A2015106045)

摘　　要：对于任意图G,G并上足够多的孤立顶点就为某个无圈有向图的竞争图.这样加进来的孤立顶点的最少个数称为图G的竞争数,记作k(G).一般来说计算图的竞争数是比较困难的,并且通过计算图的竞争数来刻画图已成为研究竞争图理论的一个重要内容.广义Halin图包括一个树的平面嵌入和一个连接树的叶子的圈.针对广义Halin图进行研究,确定了广义Halin图的竞争数.For any graph G,G together with sufficiently many isolated vertices is the competition graph of someacyclic 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 Halingraph 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.

关 键 词：竞争图 竞争数 边团覆盖数 HALIN图 广义Halin图 

分 类 号：O157.5[理学—数学]