Variations of maximum-clique transversal sets on graphs |
| |
Authors: | Chuan-Min Lee |
| |
Institution: | (1) Univ. Ca' Foscari di Venezia, di Venezia, Italy |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|