Abstract
Let $G$ be a graph on $n$ vertices. For $i\in \{0,1\}$, 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 an 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.
Moreover, we show that to decide whether $G$ has a 0-perfect forest with at least $n/2+k$ edges, where $k$ is the parameter, is W[1]-hard.
We also prove that for a prescribed edge $e$ of $G,$ it is NP-hard to obtain a 0-perfect forest containing $e,$ but one can decide if there exists
a 0-perfect forest not containing $e$ in polynomial time.
It is easy to see that every connected graph with an 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.
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 an 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.
Moreover, we show that to decide whether $G$ has a 0-perfect forest with at least $n/2+k$ edges, where $k$ is the parameter, is W[1]-hard.
We also prove that for a prescribed edge $e$ of $G,$ it is NP-hard to obtain a 0-perfect forest containing $e,$ but one can decide if there exists
a 0-perfect forest not containing $e$ in polynomial time.
It is easy to see that every connected graph with an 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.
Original language | English |
---|---|
Journal | Journal of Graph Theory |
Volume | 101 |
Issue number | 3 |
Early online date | 9 May 2022 |
Publication status | Published - 2022 |