Paper Info
Title
Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs.
Abstract
A graph G is 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.
Year
DOI
Venue
2018
10.23638/DMTCS-20-2-15
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
Keywords
Field
DocType
Decycling Matching,Decycling Set
Graph,Discrete mathematics,Combinatorics,Vertex (geometry),Hamiltonian (quantum mechanics),Chordal graph,Recognition algorithm,Mathematics
Journal
Volume
Issue
ISSN
20.0
2.0
1462-7264
Citations 
PageRank 
References 
0
0.34
0
Authors
2
Name
Order
Citations
PageRank
Fábio Protti135746.14
Uéverton S. Souza22021.12