TY - JOUR
T1 - On Seymour's and Sullivan's second neighbourhood conjectures
AU - Ai, Jiangdong
AU - Gerke, Stefanie
AU - Gutin, Gregory
AU - Wang, Shujing
AU - Yeo, Anders
AU - Zhou, Yacong
N1 - Funding Information:
We would like to thank the reviewers for carefully reading our paper and for their helpful comments and suggestions. This research by Jiangdong Ai was supported by the Fundamental Research Funds for the Central Universities, Nankai University. This research by Shujing Wang and Yacong Zhou was supported by China Scholarship Council (CSC).
PY - 2024/3
Y1 - 2024/3
N2 - For a vertex (Formula presented.) of a digraph, (Formula presented.) ((Formula presented.), respectively) is the number of vertices at distance 1 from (to, respectively) (Formula presented.) and (Formula presented.) is the number of vertices at distance 2 from (Formula presented.). In 1995, Seymour conjectured that for any oriented graph (Formula presented.) there exists a vertex (Formula presented.) such that (Formula presented.). In 2006, Sullivan conjectured that there exists a vertex (Formula presented.) in (Formula presented.) such that (Formula presented.). We give a sufficient condition in terms of the number of transitive triangles for an oriented graph to satisfy Sullivan's conjecture. In particular, this implies that Sullivan's conjecture holds for all orientations of planar graphs and triangle-free graphs. An oriented graph (Formula presented.) is an oriented split graph if the vertices of (Formula presented.) can be partitioned into vertex sets (Formula presented.) and (Formula presented.) such that (Formula presented.) is an independent set and (Formula presented.) induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when (Formula presented.) induces a regular or an almost regular tournament.
AB - For a vertex (Formula presented.) of a digraph, (Formula presented.) ((Formula presented.), respectively) is the number of vertices at distance 1 from (to, respectively) (Formula presented.) and (Formula presented.) is the number of vertices at distance 2 from (Formula presented.). In 1995, Seymour conjectured that for any oriented graph (Formula presented.) there exists a vertex (Formula presented.) such that (Formula presented.). In 2006, Sullivan conjectured that there exists a vertex (Formula presented.) in (Formula presented.) such that (Formula presented.). We give a sufficient condition in terms of the number of transitive triangles for an oriented graph to satisfy Sullivan's conjecture. In particular, this implies that Sullivan's conjecture holds for all orientations of planar graphs and triangle-free graphs. An oriented graph (Formula presented.) is an oriented split graph if the vertices of (Formula presented.) can be partitioned into vertex sets (Formula presented.) and (Formula presented.) such that (Formula presented.) is an independent set and (Formula presented.) induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when (Formula presented.) induces a regular or an almost regular tournament.
KW - oriented split graphs
KW - planar digraphs
KW - Seymour's second neighbourhood conjecture
KW - Sullivan's second neighbourhood conjecture
U2 - 10.1002/jgt.23050
DO - 10.1002/jgt.23050
M3 - Journal article
AN - SCOPUS:85174289560
SN - 0364-9024
VL - 105
SP - 413
EP - 426
JO - Journal of Graph Theory
JF - Journal of Graph Theory
IS - 3
ER -