


























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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。