有向图的结合数与计算

The Binding Number of a Digraph and its Computation

本文讨论Caccetta-Hggkvist猜想的特殊情形猜想:如果有向图D的最小顶点出度δ^+(D)≥ n/3,则D存在△。受无向图G的结合数bind(G)≥3/2是G中存在△的充分条件的启发。我们在有向图中引入结合数的概念,讨论了该参数的一些基本性质,证明了有向图D的结合数bind(D)≥(5^(1/2)+1)/2是D中存在△的充分条件,并提出了关于结合数与围长之间联系的两个猜想,其结论弱于Caccetta-Hggkvist猜想。通过转化为最大流问题,我们最后给出了有向图结合数计算的多项式算法。

The special case of Caccetta-Haggkvist＇s conjecture supposes that the minimum outdegree δ＋（D） ≥ n/3 of D is a sufficient condition that guarantees the existence of a directed triangle in D. For an undirected graph G, the binding number bind（G） ≥3/2 is a sufficient condition for G to have a triangle. In this paper, we generalize the concept of binding numbers to digraphs and discuss its basic properties. We prove that the binding number bind（D） ≥√5＋1/2 of a digraph D is a sufficient condition that guarantees the existence of a directed triangle in D. In particular, we propose two conjectures on the relationship between the binding number and the girth of D, which can be deduced from Caccetta-Haggkvist＇s Conjecture. Furthermore, we show that the binding number bind（D） can be computed in polynomial time by transforming the problem into a network flow problem.