Locating a Seymour vertex in oriented graphs having minimum outdegree at most 7

Abstract

A vertex $v$ of an oriented graph $D$ is a Seymour vertex if the number of outneighbors of $v$ is less than or equal to the number of second outneighbors of $v$ (vertices at directed distance exactly $2$ from $v$). Seymour's Second Neighborhood Conjecture claims that every oriented graph contains a Seymour vertex. We propose the following stronger conjecture (Conjecture 1.4): given any oriented graphs $D$, there exists a minimum outdegree vertex $s$, and a Seymour vertex $v^{\ast }$ such that the directed distance from $s$ to $v^{\ast }$ is at most $\lfloor \frac{{\delta }^{+}(D)}{3}\rfloor$, where ${\delta }^{+}(D)$ denotes the minimum outdegree of $D$. The main contribution of this article is to show that Conjecture 1.4 is true for all oriented graphs having minimum outdegree at most $7$. This, in particular, improves the results of Kaneko and Locke (2001) which (implicitly) proved Conjecture 1.4 for all oriented graphs having minimum outdegree at most $6$. In particular, this yields Seymour's Second Neighborhood Conjecture for this class of oriented graphs. We also construct a family of digraphs attaining the proposed distance bound, showing that it cannot be improved in general. Finally, by adapting existing arguments, we show that if Seymour's Second Neighborhood Conjecture is true then given any oriented graph $D$ and any vertex $v$, it is always possible to find a Seymour vertex $v^{\ast }$ such that the directed distance from $v$ to $v^{\ast }$ is at most the outdegree of $v$.

arXiv commentThe earlier version of our paper contained different proof technique for two cases of the proof. It involved substantial computational assistance. Whereas this version does not require any computational assistance and is completely based on handwritten logical arguments. The author list has been updated at the request of a co-author listed in the previous version