Split-Twin Extensions Preserving Seymour Vertices
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.
이 뉴스, 어떠셨어요?
탭 한 번으로 반응 · 로그인 불필요