Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4649676 | Discrete Mathematics | 2009 | 4 Pages |
Abstract
Let FF be an oriented forest with nn vertices and mm arcs and DD be a digraph without loops and multiple arcs. In this note we prove that DD contains a subdigraph isomorphic to FF if DD has at least nn vertices and min{d+(u)+d+(v),d−(u)+d−(v),d+(u)+d−(v)}≥2m−1min{d+(u)+d+(v),d−(u)+d−(v),d+(u)+d−(v)}≥2m−1 for every pair of vertices u,v∈V(D)u,v∈V(D) with uv∉A(D)uv∉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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Shengning Qiao, Shenggui Zhang,