Article ID Journal Published Year Pages File Type
6424365 European Journal of Combinatorics 2013 5 Pages PDF
Abstract

The second neighborhood conjecture of Seymour says that every antisymmetric digraph has a vertex whose second neighborhood is not smaller than the first one. The Caccetta-Häggkvist conjecture says that every digraph with n vertices and minimum out-degree r contains a cycle of length at most ⌈n/r⌉. We give a proof of the former conjecture for digraphs with out-degree r and connectivity r−1, and of the second one for digraphs with connectivity r−1 and r≥n/3. The main tool is the isoperimetric method of Hamidoune.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,