Note on Perfect Forests in Digraphs

Gregory Gutin, Anders Yeo

Research output: Contribution to journalArticlepeer-review

77 Downloads (Pure)

Abstract

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree inline image of each vertex x in F is odd, and each tree of F is an induced subgraph of G. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph G contains a perfect forest if and only if G has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP-hard, for the three others this problem is polynomial-time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.
Original languageEnglish
Pages (from-to)372-377
Number of pages6
JournalJournal of Graph Theory
Volume85
Issue number2
Early online date17 Jun 2016
DOIs
Publication statusE-pub ahead of print - 17 Jun 2016

Cite this