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* such that the directed distance from s to v* is at most ⌊(δ+(D))/3 ⌋, where δ+(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* such that the directed distance from v to v* is at most the outdegree of v.
Related
- Fisher Information and the Minimum Mean-Square Error for Locating Closely Spaced Point Sources
- A note on partitioning the vertex set of a graph into a dominating set and a locating dominating set
- Minimum-makespan completion and vertex selection leave the Wang-Sitters constant at 11/6
- Degreewise Cut-Semigroup Saturation for K5-Minor-Free Graphs and Seymour's Planar Edge-Colouring Conjecture
- Powers of Hamiltonian Cycles in Randomly Augmented Pósa-Seymour Graphs
BibTeX
@misc{sadhukhan2026locating,
title = {{Locating a Seymour vertex in oriented graphs having minimum outdegree at most 7}},
author = {Arpan Sadhukhan and Sagnik Sen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.30588},
eprint = {2606.30588},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.30588},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Locating a Seymour vertex in oriented graphs having minimum outdegree at most 7
AU - Arpan Sadhukhan
AU - Sagnik Sen
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2606.30588
UR - https://arxiv.org/abs/2606.30588
AB - 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^* such that the directed distance from s to v^* is at most ⌊(δ^+(D))/3 ⌋, where δ^+(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^* such that the directed distance from v to v^* is at most the outdegree of v.
ER -