This conjecture has been formulated some time in the 1980's. It is related to the Caccetta-Haggkvist Conjecture (special case for digraphs in which all in and out-degrees are n/3). More on the CHC will appear in one or more related problems later this year.
If G is a digraph and v is a vertex of G, the first neighborhood of v consists of all out-neighbors of v, and the second neighborhood consists of all vertices that are not in the first neighborhood but can be reached from v by a directed path of length 2.
Conjecture 1: Every digraph without loops and digons has a vertex v whose second neighborhood contains at least as many vertices as its first neighborhood.
The conjecture has been verified for tournaments - Fisher [2] proved it using algebraic methods. A combinatorial proof was obtained by Havet and Thomasse [3]. Kaneko and Locke [4] proved it for all digraphs with minimum outdegree at most 6. Chen, Shen and Yuster [1] proved that there is a vertex v whose second neighborhood has at least c times as many vertices as the first one, where c = 0.657298... Besides these results, not much is known.
Bibliography:
[1] Chen, Guantao; Shen, Jian; Yuster, Raphael. Second neighborhood via first neighborhood in digraphs. Ann. Comb. 7 (2003), 15-20.
[2] Fisher, David C. Squaring a tournament: a proof of Dean's conjecture. J. Graph Theory 23 (1996), 43-48.
[3] Havet, Frédéric; Thomassé, Stéphan. Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture. J. Graph Theory 35 (2000), 244-256.
[4] Kaneko, Yoshihiro; Locke, Stephen C. The minimum degree approach for Paul Seymour's distance 2 conjecture. Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001). Congr. Numer. 148 (2001), 201-206.
Send comments to Bojan.Mohar@uni-lj.si