Article ID Journal Published Year Pages File Type
420314 Discrete Applied Mathematics 2006 12 Pages PDF
Abstract

In this paper, we show that the clique-transversal number τC(G)τC(G) and the clique-independence number αC(G)αC(G) are equal for any distance-hereditary graph G  . As a byproduct of proving that τC(G)=αC(G)τC(G)=αC(G), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,