Directed triangles in digraphs

被引：30

作者：

Shen, J ^{[1
]}

机构：

[1] Queens Univ, Dept Math & Stat, Kingston, ON K7L 3N6, Canada

来源：

JOURNAL OF COMBINATORIAL THEORY SERIES B | 1998年 / 74卷 / 02期

关键词：

D O I：

10.1006/jctb.1998.1839

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let c be the smallest possible value such that every digraph on n vertices with minimum outdegree at least nl contains a directed triangle. It was conjectured by Caccetta and Haggkvist in 1978 that c = 1/3. Recently Bondy showed that c less than or equal to (2 root 6-3)/5 = 0.3797... by using some counting arguments. In this note, we prove that c less than or equal to 3 - root 7 = 0.3542.... (C) 1998 Academic Press.

引用

页码：405 / 407

页数：3