Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420314 | Discrete Applied Mathematics | 2006 | 12 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chuan-Min Lee, Maw-Shang Chang,