zbMATH — the first resource for mathematics

Remarks on the second neighborhood problem. (English) Zbl 1122.05040
Summary: The second neighborhood conjecture of Seymour asserts that for any orientation \(G = (V,E)\), there exists a vertex \(v \in V\) so that \(|N^{+}(v)| \leq |N^{++}(v)|\). The conjecture was resolved by D. C. Fisher [J. Graph Theory 23, 43–48 (1996; Zbl 0857.05042)] 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.

05C20 Directed graphs (digraphs), tournaments
Full Text: DOI
[1] Dean, Congressus Numerantium 109 pp 73– (1995)
[2] Fisher, J Graph Theory 23 pp 43– (1996)
[3] Chen, Annals Combin 7 pp 15– (2003) · doi:10.1007/s000260300001
[4] Havet, J Graph Theory 35 pp 244– (2000)
[5] Kaneko, Congressus Numerantium 148 pp 201– (2001)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.