无爪图上团横贯数的界  

The bound of clique-transversal numbers in claw-free graphs

作　　者：梁作松[1] 单而芳[2] 管梅[3] 

机构地区：[1]上海大学数学系,上海200444 [2]上海大学管理学院,上海200444 [3]合肥学院数学与物理系,合肥230601

出　　处：《运筹学学报》2013年第2期35-40,共6页Operations Research Transactions

基　　金：国家自然科学基金(No.11171207);安徽省高等学校省级优秀青年人才基金(No.2012SQRL170)

摘　　要：设G=(V,E)为简单图,图G的每个至少有两个顶点的极大完全子图称为G的一个团.一个顶点子集S(?)V称为图G的团横贯集,如果S与G的所有团都相交,即对于G的任意的团C有S∩V(C)≠φ.图G的团横贯数是图G的最小团横贯集所含顶点的数目,记为τ_C(G).证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.A clique-transversal set S of a graph G = （V,E） is a subset of vertices of G such that S meets all cliques of G, where a clique is defined as a complete subgraph maximal under inclusion and having at least two vertices. The clique-transversal number, of G denoted by TC（G）, is the minimum cardinality of a clique-transversal set in G. In this paper we discuss the bound of clique-transversal numbers in several subclasses of claw-free graphs.

关 键 词：团横贯数 团横贯集 无爪图 界 

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