2026-07-22T11:12:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14494 2024-03-06T10:54:09Z ddc:004 open_access

Perfect Forests in Graphs and Their Extensions Gutin, Gregory Yeo, Anders graphs odd degree subgraphs perfect forests polynomial algorithms Let G be a graph on n vertices. For i ∈ {0,1} and a connected graph G, a spanning forest F of G is called an i-perfect forest if every tree in F is an induced subgraph of G and exactly i vertices of F have even degree (including zero). An i-perfect forest of G is proper if it has no vertices of degree zero. Scott (2001) showed that every connected graph with even number of vertices contains a (proper) 0-perfect forest. We prove that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges. We also prove that for a prescribed edge e of G, it is NP-hard to obtain a 0-perfect forest containing e, but we can find a 0-perfect forest not containing e in polynomial time. It is easy to see that every graph with odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We give a characterization of when a connected graph has a proper 1-perfect forest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gregory Gutin and Anders Yeo 2021 Is Part Of LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2021.54 urn:nbn:de:0030-drops-144947 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.54 eng https://creativecommons.org/licenses/by/4.0/legalcode