| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 419202 | Discrete Applied Mathematics | 2016 | 7 Pages |
Abstract
A cycle transversal or feedback vertex set of a graph GG is a subset T⊆V(G)T⊆V(G) such that T∩V(C)≠0̸T∩V(C)≠0̸ for every cycle CC of GG. A clique cycle transversal, or cct for short, is a cycle transversal which is a clique. Recognizing graphs which admit a cct can be done in polynomial time; however, no structural characterization of such graphs is known. We characterize distance-hereditary graphs admitting a cct in terms of forbidden induced subgraphs. This extends similar results for chordal graphs and cographs.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andreas Brandstädt, Simone Esposito, Loana T. Nogueira, Fábio Protti,