东篱科研大数据发现系统（DRDS）

位置：成果数据库 > 期刊 > 期刊详情页

无爪图上团横贯数的界

ISSN号：1007-6093
期刊名称：运筹学学报
时间：2013.6.15
页码：35-40
分类：O157.6[理学—数学;理学—基础数学]
作者机构：[1]上海大学数学系,上海200444, [2]上海大学管理学院,上海200444, [3]合肥学院数学与物理系,合肥230601
相关基金：国家自然科学基金（No.11171207）,安徽省高等学校省级优秀青年人才基金（No.2012SQRL170）
相关项目：图的子图横贯与子图回避染色

关键词：团横贯数, 团横贯集, 无爪图, 界, clique-transversal number, clique-transversal set, claw-free graph, bound

中文摘要：

设G=（VE）为简单图，图G的每个至少有两个顶点的极大完全子图称为G的一个团．一个顶点子集S∈y称为图G的团横贯集，如果S与G的所有团都相交，即对于G的任意的团C有S∩（C）≠φ．图G的团横贯数是图G的最小团横贯集所含顶点的数目，记为TG（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.

同期刊论文项目