Abstract | ||
---|---|---|
A cycle transversal or feedback vertex set of a graph G is a subset T ź V ( G ) such that T ź V ( C ) ź 0ź for every cycle C of G . 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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.dam.2014.12.007 | Electronic Notes in Discrete Mathematics |
Keywords | DocType | Volume |
feedback vertex set | Journal | abs/1302.1402 |
Issue | ISSN | Citations |
C | 0166-218X | 0 |
PageRank | References | Authors |
0.34 | 5 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Andreas Brandstädt | 1 | 1306 | 129.88 |
Simone Esposito | 2 | 0 | 0.34 |
Loana Tito Nogueira | 3 | 163 | 11.94 |
Fábio Protti | 4 | 357 | 46.14 |