无爪图上团横贯数的界

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 35-40.

无爪图上团横贯数的界

梁作松¹，单而芳^2,*，管梅³

1. 上海大学数学系，上海 200444 2. 上海大学管理学院，上海 200444 3. 合肥学院数学与物理系，合肥 230601

收稿日期:2012-11-21 出版日期:2013-06-15 发布日期:2013-06-15
通讯作者: 单而芳 E-mail:efshan@shu.edu.cn
基金资助:
国家自然科学基金 (No. 11171207), 安徽省高等学校省级优秀青年人才基金 (No. 2012SQRL170)

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

LIANG Zuosong¹,SHAN Erfang^2,*,GUAN Mei³

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

Received:2012-11-21 Online:2013-06-15 Published:2013-06-15

摘要/Abstract

摘要： 设 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-连接图这三类无爪图的团横贯数不超过其阶数的一半.

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

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.

Key words: clique-transversal number, clique-transversal set, claw-free graph, bound

中图分类号:

O157.6

梁作松，单而芳，管梅. 无爪图上团横贯数的界[J]. 运筹学学报, 2013, 17(2): 35-40.

LIANG Zuosong,SHAN Erfang,GUAN Mei. The bound of clique-transversal numbers in claw-free graphs[J]. Operations Research Transactions, 2013, 17(2): 35-40.

参考文献

Bondy J A, Murty U S R. Graph Theory [M]. Berlin: Springer, 2008.
King A D. Hitting all maximum cliques with a stable set using lopsided independent transversals [J]. Journal of Graph Theory, 2010, 67: 300-305.
Erd\H{o}s P, Gallai T, Tuza Z. Covering the cliques of a graph with vertices [J]. Discrete Math, 1992, 108: 279-289.
Chang G J, Farber M, Tuza Z. Algorithmic aspects of neighbourhood number [J]. SIAM J Discrete Math, 1993, 6: 24-29.
Guruswami V, Rangan C P. Algorithmic aspects of clique-transversal and clique-independent sets [J]. Discrete Appl Math, 2000, 100: 183-202.
Balachandhran V, Nagavamsi P,   Rangan C P. Clique transversal and clique independence on comparability graphs [J]. Information Processing Letters, 1996, 58: 181-184.
Lee C M, Chang M S. Distance-hereditary graphs are clique-perfect [J]. Discrete Appl Math, 2006, 154: 525-536.
Andreae T, Schughart M, Tuza Z. Clique-transversal sets of line graphs and complements of line graphs [J]. Discrete Math, 1991, 88: 11-20.
Bacs\'o G, Gravier S, Gy\'arf\'as A, et al. Coloring the maximal cliques of graphs [J]. SIAM J Discrete Math, 2004, 17: 361-376.
Bacs\'o G, Tuza Z. Clique-transversal sets and weak 2-colorings in graphs of small maximum degree [J]. Discrete Mathematics and Theoretical Computer Science, 2009, 11: 15-24.
Andreae T. On the clique-transversal number of chordal graphs [J]. Discrete Math, 1998, 191: 3-11.
Bonomo F, Chudnovsky M, Dur\'{a}n G. Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs [J]. Discrete Appl Math, 2008, 156: 1058-1082.
Dur\'{a}n G, Lin M C,   Szwarcfiter J L. On clique-transversals and clique-independent sets [J]. Annals of Operations Research, 2002, 116: 71-77.
Lakshmanan S A, Vijayakumar A. The $\langle t \rangle$-property of some classes of graphs [J]. Discrete Math, 2008, 309: 259-263.
Liang Z S, Shan E F. Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs [J]. Information Processing Letters, 2011, 111: 1104-1107.
Shan E F, Cheng T C E, Kang L Y. Bounds on the clique-transversal number of regular graphs [J]. Science in China A: Mathematics, 2008, 51: 851-863.
Tuza Z. Covering all cliques of a graph [J]. Discrete Math., 1990, 86: 117-126.
Chudnovsky M, Seymour P.   Claw-free graphs IV. Decomposition theorem [J]. J. Combin. Theory Ser. B, 2008, 98: 839-938.
Chudnovsky M, Seymour P.   Claw-free graphs III. Circular interval graphs [J]. J. Combin. Theory Ser. B, 2008, 98: 812-834.
Cerioli M R, Korenchendler A L. Clique-coloring circular-arc graphs [J]. Electronic Notes in Discrete Mathematics, 2009, 35: 287-292.

[1]	任烨权, 白延琴, 李倩, 余长君, 张连生. 一个求解池化问题的二阶锥逼近算法[J]. 运筹学学报, 2020, 24(2): 61-72.
[2]	李文华, 翟威娜, 柴幸, 高超. 具有两个不相容工件族单位工件的有界分批在线排序问题[J]. 运筹学学报, 2019, 23(4): 105-110.
[3]	陶艳亮, 黄琼湘, 陈琳. 图的区间边着色的收缩图方法[J]. 运筹学学报, 2019, 23(2): 31-43.
[4]	刘岩, 雷梦霞, 黄晓娴. 最大匹配的路变换图[J]. 运筹学学报, 2019, 23(2): 104-112.
[5]	蔡爽, 杨珂, 刘克. 具有机器适用限制的分布式置换流水车间问题的模型与算法[J]. 运筹学学报, 2018, 22(4): 17-30.
[6]	高雷阜, 张亚红. 对称锥互补问题的一类惩罚FB函数[J]. 运筹学学报, 2018, 22(3): 125-131.
[7]	何斯迈, 金羽佳, 王华, 葛冬冬. 在线学习方法综述: 汤普森抽样和其他方法[J]. 运筹学学报, 2017, 21(4): 84-102.
[8]	李姗, 单而芳, 张琳. 5-正则图的全控制数的一个注记[J]. 运筹学学报, 2017, 21(1): 125-128.
[9]	郑伟, 王力工. 无爪图中不相邻子图P_4和K_1的度和条件下的哈密尔顿性[J]. 运筹学学报, 2016, 20(1): 112-117.
[10]	黄晓娴, 刘岩, 吴博思. 关于分数k-因子临界图与分数k-可扩图的若干结果[J]. 运筹学学报, 2016, 20(1): 125-130.
[11]	潘平奇. 关于“线性规划界面算法的高效实现”[J]. 运筹学学报, 2015, 19(3): 78-84.
[12]	刘元文, 欧宜贵. 求解带界约束的非线性方程组的混合方法[J]. 运筹学学报, 2015, 19(1): 45-56.
[13]	张惠珍, 魏欣, 马良. 求解0-1线性整数规划问题的有界单纯形法[J]. 运筹学学报, 2014, 18(3): 71-78.
[14]	冯增哲, 张西学, 刘建波, 房亮. 半定规划的一个新的宽邻域非可行内点算法[J]. 运筹学学报, 2014, 18(2): 49-58.
[15]	李巧, 刘岩. 分数k-因子临界图的条件[J]. 运筹学学报, 2013, 17(4): 123-130.