The Binding Number of a Digraph

Genjiu Xu, Xueliang Li and Shenggui Zhang
Department of Applied Mathematics, Northwestern Polytechnical University,
Xi'an 710072,
P.R.China

Abstract    
The binding number of graphs was introduced by Woodall. It was conjectured by Woodall and later proved by Shi that a graph with binding number at least 3/2 contains a triangle. In this paper, motivated by the concept of binding number of graphs, we introduce the binding number of digraphs. Some basic results on this parameter are obtained and it is shown that a digraph with binding number at least contains a directed triangle. We also pose two conjectures on the girth of digraphs in terms of the binding number. These conjectures are closely related to the Caccetta-Häggkvist Conjecture which is on the girth of digraphs in terms of degrees of vertices.