Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6424365 | European Journal of Combinatorics | 2013 | 5 Pages |
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
Anna Lladó,