Split-Twin Extensions Preserving Seymour Vertices

Read full text
Authors: Stanisław Marek Halkiewicz
Cited by: 0

Abstract

The Second Neighborhood Conjecture of Seymour asserts that every oriented graph contains a vertex~$v$ satisfying $|\Npp(v)|\ge|\Np(v)|$. We introduce \emph{Pisa graphs} -- strongly connected oriented graphs~$D$ with $Δ(D)=\max_{v\in V(D)}\bigl(|\Npp(v)|-|\Np(v)|\bigr)=0$ -- named after the Leaning Tower of Pisa, as these graphs stand at the precise boundary between satisfying and potentially violating the conjecture. We prove that a Pisa graph containing a vertex of outdegree one must have underlying graph~$C_n$. We verify computationally that every Pisa graph on at most seven vertices has underlying graph isomorphic to either~$C_n$ or~$K_n$ minus a matching, and conjecture this holds in general. Partial structural results are presented, including a decomposition formula for the sum of all vertex margins, and a connection to blowup constructions for potential counterexamples due to Zelenskyi, Darmosiuk and Nalivayko.

Fields of Study & Subjects

Advanced Graph Theory Research Limits and Structures in Graph Theory Complexity and Algorithms in Graphs

Publication details

Journal / source
arXiv (Cornell University)
Publication date
29 January 2026
Document type
Preprint