## 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 |