Fábio Protti ; Uéverton S. Souza - 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 - https://doi.org/10.23638/DMTCS-20-2-15
Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphsArticle

Authors: Fábio Protti ; Uéverton S. Souza ORCID

    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.


    Volume: vol. 20 no. 2
    Section: Graph Theory
    Published on: November 20, 2018
    Accepted on: October 24, 2018
    Submitted on: October 19, 2017
    Keywords: Computer Science - Discrete Mathematics

    2 Documents citing this article

    Consultation statistics

    This page has been seen 581 times.
    This article's PDF has been downloaded 352 times.