摘要
设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.
出处
《运筹学学报》
CSCD
北大核心
2013年第2期35-40,共6页
Operations Research Transactions
基金
国家自然科学基金(No.11171207)
安徽省高等学校省级优秀青年人才基金(No.2012SQRL170)
关键词
团横贯数
团横贯集
无爪图
界
clique-transversal number
clique-transversal set
claw-free graph
bound
