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 |
| _version_ | 1797270049007861760 |
|---|---|
| author | Fábio Protti Uéverton S. Souza |
| author_facet | Fábio Protti Uéverton S. Souza |
| author_sort | Fábio Protti |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:58:05Z |
| format | Article |
| id | doaj.art-06c5685eef1d426bb9a0214da50531f9 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:05Z |
| publishDate | 2018-11-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-06c5685eef1d426bb9a0214da50531f92024-03-07T15:37:21ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502018-11-01vol. 20 no. 2Graph Theory10.23638/DMTCS-20-2-153998Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphsFábio ProttiUéverton S. Souzahttps://orcid.org/0000-0002-5320-9209A 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.https://dmtcs.episciences.org/3998/pdfcomputer science - discrete mathematics |
| spellingShingle | 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 Discrete Mathematics & Theoretical Computer Science computer science - discrete mathematics |
| title | Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs |
| title_full | Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs |
| title_fullStr | Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs |
| title_full_unstemmed | Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs |
| title_short | Decycling a graph by the removal of a matching: new algorithmic and structural aspects in some classes of graphs |
| title_sort | decycling a graph by the removal of a matching new algorithmic and structural aspects in some classes of graphs |
| topic | computer science - discrete mathematics |
| url | https://dmtcs.episciences.org/3998/pdf |
| work_keys_str_mv | AT fabioprotti decyclingagraphbytheremovalofamatchingnewalgorithmicandstructuralaspectsinsomeclassesofgraphs AT uevertonssouza decyclingagraphbytheremovalofamatchingnewalgorithmicandstructuralaspectsinsomeclassesofgraphs |