首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 nn vertices and minimum out-degree rr contains a cycle of length at most ⌈n/r⌉n/r. We give a proof of the former conjecture for digraphs with out-degree rr and connectivity r−1r1, and of the second one for digraphs with connectivity r−1r1 and r≥n/3rn/3. The main tool is the isoperimetric method of Hamidoune.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号