On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity |
| |
Authors: | Anna Lladó |
| |
Institution: | Universitat Politècnica de Catalunya, BarcelonaTech, Spain |
| |
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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|