Premium
Remarks on the second neighborhood problem
Author(s) -
Fidler D.,
Yuster R.
Publication year - 2007
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20229
Subject(s) - conjecture , mathematics , combinatorics , vertex (graph theory) , collatz conjecture , graph , lonely runner conjecture , orientation (vector space) , discrete mathematics , geometry
The second neighborhood conjecture of Seymour asserts that for any orientation G = ( V , E ), there exists a vertex υ ∈ V so that | N + (υ)| ≤ | N ++ (υ)|. The conjecture was resolved by Fisher for tournaments. In this article, we prove the second neighborhood conjecture for several additional classes of dense orientations. We also prove some approximation results, and reduce an asymptotic version of the conjecture to a finite case. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 208–220, 2007