Note on Perfect forests in Digraphs

Gregory Gutin, Anders Yeo

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

A spanning subgraph F of a graph G is called perfect if F is a forest, the degree dF(X) 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
JournalJournal of Graph Theory
Volume85
Issue number2
Pages (from-to)372-377
ISSN0364-9024
DOIs
Publication statusPublished - 2017
Externally publishedYes

Keywords

  • degree parity
  • digraphs
  • directed forests
  • perfect forests

Fingerprint

Dive into the research topics of 'Note on Perfect forests in Digraphs'. Together they form a unique fingerprint.

Cite this