ISRN Discrete Mathematics
Volume 2011 (2011), Article ID 540834, 20 pages
doi:10.5402/2011/540834
Research Article

Weighted Maximum-Clique Transversal Sets of Graphs

Chuan-Min Lee

Department of Computer and Communication Engineering, Ming Chuan University, 5 De Ming Road, Guishan District, Taoyuan County 333, Taiwan

Received 16 November 2011; Accepted 26 December 2011

Academic Editors: E. Cheng, A. Pรชcher, and E. Tomita

Copyright © 2011 Chuan-Min Lee. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

A maximum-clique transversal set of a graph ๐บ is a subset of vertices intersecting all maximum cliques of ๐บ . The maximum-clique transversal set problem is to find a maximum-clique transversal set of ๐บ 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 study the weighted version of the maximum-clique transversal set problem for split graphs, balanced graphs, strongly chordal graph, Helly circular-arc graphs, comparability graphs, distance-hereditary graphs, and graphs of bounded treewidth.