Triangle Counts Extend Sullivan’s Second Neighbourhood Conjecture

Second-neighbourhood conjectures ask for a local imbalance that should exist somewhere in every oriented graph. Seymour’s version predicts a vertex $x$ with $d^+(x) \leq d^{++}(x)$; Sullivan’s asks for a vertex with $d^-(x) \leq d^{++}(x)$. Both are easy to state and hard to settle, because the second out-neighbourhood mixes local orientation choices with paths of length 2 across the whole digraph.

This paper gives new positive cases rather than a full proof. Its main advance is a sufficient condition for Sullivan’s conjecture expressed through the number of transitive triangles in an oriented graph. From that condition, the authors derive two clean corollaries: Sullivan’s conjecture holds for all orientations of planar graphs and for all orientations of triangle-free graphs. They also study oriented split graphs, where the vertex set is partitioned into an independent set $X$ and a tournament $Y$, and prove both Seymour’s and Sullivan’s conjectures for selected families.

Core Contribution

The central idea is to connect Sullivan’s in-neighbourhood inequality to the supply of transitive triangles. A transitive triangle is a directed triangle whose orientation is acyclic, so it contains a vertex that reaches the other two along directed edges. Counting such configurations gives the proof a way to control when the desired comparison between first in-neighbours and second out-neighbours must hold.

That matters because Sullivan’s conjecture is a separate condition from Seymour’s: it compares $d^-(x)$ to $d^{++}(x)$ rather than comparing $d^+(x)$ to $d^{++}(x)$. The paper does not claim to reduce Sullivan’s conjecture to Seymour’s. Instead, it gives a counting condition that can be checked in graph classes where the undirected structure limits triangles. Triangle-free orientations make the condition especially direct, while planar orientations benefit from sparsity restrictions that constrain the possible triangle structure.

Technical Approach

The proofs are combinatorial. The paper works with standard directed-neighbourhood notation: $N^+(x)$ and $N^-(x)$ for first out- and in-neighbours, and $N^{++}(x)$ for vertices reachable from $x$ by a directed path of length 2. The target inequalities compare the sizes $d^+(x)$, $d^-(x)$, and $d^{++}(x)$.

For oriented split graphs, the partition $V(D)=X\cup Y$ is the main structural handle. The set $X$ is independent, while $D[Y]$ is a tournament, so the difficulty is how vertices in $X$ attach to the tournament side. The split-graph proofs use this partition to compare degrees and second-neighbourhood sizes across the independent and tournament parts, rather than treating the graph as an arbitrary orientation.

The split-graph results are strongest when the tournament side is regular or almost regular. That assumption gives degree balance inside $Y$, which is useful when comparing in-degree, out-degree, and second-neighbourhood size across the partition.

Results and Analysis

The supported results are theorem-level rather than experimental. The paper proves Sullivan’s conjecture under its transitive-triangle sufficient condition, then applies it to two broad graph classes: all orientations of planar graphs and all orientations of triangle-free graphs. The triangle-free case is especially clean because the relevant triangle count is tightly constrained. The planar case is more informative: it says that even when triangles may exist, the planar host graph has enough structural sparsity for the condition to force a Sullivan vertex.

The second set of results concerns oriented split graphs. Here the authors prove both Seymour’s and Sullivan’s conjectures for some families, including cases where $Y$ induces a regular or almost regular tournament. This is a narrower contribution than the planar and triangle-free corollaries, but it attacks a natural test class: oriented split graphs sit close to tournaments while allowing an independent side that can disrupt tournament-style arguments.

The evidence is a formal proof, so the main question is scope rather than statistical strength. The paper advances the boundary of known positive cases but does not resolve either conjecture in full. Its split-graph theorems are stated for particular families, not for every oriented split graph.

Limitations

The paper does not prove either second-neighbourhood conjecture for all oriented graphs. Its transitive-triangle condition is useful when the underlying graph class makes the count manageable, but it is not presented as a complete characterization. The split-graph analysis also depends on additional structure, such as regularity or near-regularity of the tournament part, leaving broader split-graph cases outside the proved results.