有向图的结合数与计算* (2007年)

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