Protti, Fábio and Souza, Uéverton S. - Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs

dmtcs:3998 - Discrete Mathematics & Theoretical Computer Science, November 20, 2018, vol. 20 no. 2
Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs

Authors: Protti, Fábio and Souza, Uéverton S.

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.


Source : oai:arXiv.org:1707.02473
Volume: vol. 20 no. 2
Section: Graph Theory
Published on: November 20, 2018
Submitted on: October 19, 2017
Keywords: Computer Science - Discrete Mathematics


Share