On Seymour's and Sullivan's second neighbourhood conjectures

  • Jiangdong Ai
  • , Stefanie Gerke
  • , Gregory Gutin
  • , Shujing Wang
  • , Anders Yeo
  • , Yacong Zhou

Research output: Contribution to journalArticlepeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)413-426
Number of pages14
JournalJournal of Graph Theory
Volume105
Issue number3
DOIs
Publication statusPublished - Mar 2024
Externally publishedYes

Keywords

  • Seymour's second neighbourhood conjecture
  • Sullivan's second neighbourhood conjecture
  • oriented split graphs
  • planar digraphs

ASJC Scopus subject areas

  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'On Seymour's and Sullivan's second neighbourhood conjectures'. Together they form a unique fingerprint.

Cite this