Article ID Journal Published Year Pages File Type
4649676 Discrete Mathematics 2009 4 Pages PDF
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
, ,