Degree sum conditions for oriented forests in digraphs

Shengning Qiao, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

Let F be an oriented forest with n vertices and m arcs and D be a digraph without loops and multiple arcs. In this note we prove that D contains a subdigraph isomorphic to F if D has at least n vertices and min {d+ (u) + d+ (v), d- (u) + d- (v), d+ (u) + d- (v)} ≥ 2 m - 1 for every pair of vertices u, v ∈ V (D) with u v ∉ A (D). This is a common generalization of two results of Babu and Diwan, one on the existence of forests in graphs under a degree sum condition and the other on the existence of oriented forests in digraphs under a minimum degree condition.

Original languageEnglish
Pages (from-to)4642-4645
Number of pages4
JournalDiscrete Mathematics
Volume309
Issue number13
DOIs
StatePublished - 6 Jul 2009

Keywords

  • Degree sum conditions
  • Oriented forests
  • Subdigraphs

Cite this