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 $\Delta(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.
| Subjects: | Combinatorics (math.CO) |
| MSC classes: | 05C20, 05C75 |
| Cite as: | arXiv:2601.21563 [math.CO] |
| (or arXiv:2601.21563v3 [math.CO] for this version) | |
| https://doi.org/10.48550/arXiv.2601.21563 arXiv-issued DOI via DataCite |
From: Stanisław Halkiewicz [view email]
[v1]
Thu, 29 Jan 2026 11:27:09 UTC (13 KB)
[v2]
Thu, 12 Mar 2026 18:02:26 UTC (8 KB)
[v3]
Thu, 21 May 2026 20:34:22 UTC (10 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。