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 language | English |
---|---|
Pages (from-to) | 4642-4645 |
Number of pages | 4 |
Journal | Discrete Mathematics |
Volume | 309 |
Issue number | 13 |
DOIs | |
State | Published - 6 Jul 2009 |
Keywords
- Degree sum conditions
- Oriented forests
- Subdigraphs