| 无爪图上团横贯数的界 |
| |
| 引用本文： | 梁作松,单而芳,管梅.无爪图上团横贯数的界[J].运筹学学报,2013,17(2):35-40. |
| |
| 作者姓名： | 梁作松 单而芳 管梅 |
| |
| 作者单位： | 1. 上海大学数学系，上海 200444 2. 上海大学管理学院，上海 200444 3. 合肥学院数学与物理系，合肥 230601 |
| |
| 基金项目： | 国家自然科学基金，安徽省高等学校省级优秀青年人才基金 |
| |
| 摘 要： | 设 G=(V,E) 为简单图，图 G 的每个至少有两个顶点的极大完全子图称为 G 的一个团. 一个顶点子集 S\subseteq V 称为图 G 的团横贯集, 如果 S 与 G 的所有团都相交，即对于 G 的任意的团 C 有 S\cap{V(C)}\neq\emptyset. 图 G 的团横贯数是图 G 的最小团横贯集所含顶点的数目，记为~${\large\tau}_{C}(G)$. 证明了棱柱图的补图(除5-圈外)、非奇圈的圆弧区间图和 Hex-连接图这三类无爪图的团横贯数不超过其阶数的一半.
|
| 关 键 词： | 团横贯数 团横贯集 无爪图 界 |
| 收稿时间： | 2012-11-21 |
The bound of clique-transversal numbers in claw-free graphs |
| |
| LIANG Zuosong
,
SHAN Erfang
,
GUAN Mei.The bound of clique-transversal numbers in claw-free graphs[J].OR Transactions,2013,17(2):35-40. |
| |
| Authors: | LIANG Zuosong SHAN Erfang GUAN Mei |
| |
| Institution: | 1. Department of Mathematics, Shanghai University, Shanghai 200444, China 2. School of Management, Shanghai University, Shanghai 200444, China 3. Department of Mathematics and Physics, Hefei College, Hefei 230601, China |
| |
| Abstract: | 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 $\tau_C(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. |
| |
| Keywords: | clique-transversal number clique-transversal set claw-free graph bound |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
