Variations of maximum-clique transversal sets on graphs

被引:0
作者
Chuan-Min Lee
机构
[1] Ming Chuan University,Department of Computer and Communication Engineering
来源
Annals of Operations Research | 2010年 / 181卷
关键词
Maximum-clique transversal function; Maximum-clique perfect; Signed maximum-clique transversal; Minus maximum-clique transversal; Hereditary clique-Helly graphs; Dually chordal graphs; Distance-hereditary graphs;
D O I
暂无
中图分类号
学科分类号
摘要
A maximum-clique transversal set of a graph G is a subset of vertices intersecting all maximum cliques of G. The maximum-clique transversal set problem is to find a maximum-clique transversal set of G of minimum cardinality. Motivated by the placement of transmitters for cellular telephones, Chang, Kloks, and Lee introduced the concept of maximum-clique transversal sets on graphs in 2001. In this paper, we introduce the concept of maximum-clique perfect and some variations of the maximum-clique transversal set problem such as the {k}-maximum-clique, k-fold maximum-clique, signed maximum-clique, and minus maximum-clique transversal problems. We show that balanced graphs, strongly chordal graphs, and distance-hereditary graphs are maximum-clique perfect. Besides, we present a unified approach to these four problems on strongly chordal graphs and give complexity results for the following classes of graphs: split graphs, balanced graphs, comparability graphs, distance-hereditary graphs, dually chordal graphs, doubly chordal graphs, chordal graphs, planar graphs, and triangle-free graphs.
引用
收藏
页码:21 / 66
页数:45
相关论文
共 92 条
  • [1] Andreae T.(1998)On the clique-transversal number of chordal graphs Discrete Mathematics 191 3-11
  • [2] Andreae T.(1996)On covering all cliques of a chordal graph Discrete Mathematics 149 299-302
  • [3] Flotow C.(1991)Clique transversal sets of line graphs and complements of line graphs Discrete Mathematics 88 11-20
  • [4] Andreae T.(1996)Clique transversal and clique independence on comparability graphs Information Processing Letters 58 181-184
  • [5] Schughart M.(1986)Distance hereditary graphs Journal of Combinatorial Theory. Series B 41 182-208
  • [6] Tuza Zs.(1970)Sur un Théorème du type König pour hypergraphes Annals of the New York Academy of Sciences 175 32-40
  • [7] Balachandran V.(2006)On balanced graphs Mathematical Programming 105 233-250
  • [8] Nagavamsi P.(2006)On clique-perfect and K-perfect graphs Ars Combinatoria 80 97-112
  • [9] Rangan C. P.(2008)Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs Discrete Applied Mathematics 156 1058-1082
  • [10] Bandelt H. J.(2009)Partial characterizations of clique-perfct graphs II: Diamond-free and Helly circular-arc graphs Discrete Mathematics 10 109-127