Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs
A graph $G$ is {\em matching-decyclable} if it has a matching $M$ such that $G-M$ is acyclic. Deciding whether $G$ is matching-decyclable is an NP-complete problem even if $G$ is 2-connected, planar, and subcubic. In this work we present results on matching-decyclability in the following classes: Ha...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2018-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3998/pdf |
| Summary: | A graph $G$ is {\em matching-decyclable} if it has a matching $M$ such that
$G-M$ is acyclic. Deciding whether $G$ is matching-decyclable is an NP-complete
problem even if $G$ is 2-connected, planar, and subcubic. In this work we
present results on matching-decyclability in the following classes: Hamiltonian
subcubic graphs, chordal graphs, and distance-hereditary graphs. In Hamiltonian
subcubic graphs we show that deciding matching-decyclability is NP-complete
even if there are exactly two vertices of degree two. For chordal and
distance-hereditary graphs, we present characterizations of
matching-decyclability that lead to $O(n)$-time recognition algorithms. |
|---|---|
| ISSN: | 1365-8050 |