Opuscula Math. 39, no. 6 (2019), 765-772
https://doi.org/10.7494/OpMath.2019.39.6.765

Opuscula Mathematica

# Vertices with the second neighborhood property in Eulerian digraphs

Michael Cary

Abstract. The Second Neighborhood Conjecture states that every simple digraph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood, i.e. a vertex with the Second Neighborhood Property. A cycle intersection graph of an even graph is a new graph whose vertices are the cycles in a cycle decomposition of the original graph and whose edges represent vertex intersections of the cycles. By using a digraph variant of this concept, we prove that Eulerian digraphs which admit a simple cycle intersection graph not only adhere to the Second Neighborhood Conjecture, but that local simplicity can, in some cases, also imply the existence of a Seymour vertex in the original digraph.

Keywords: Eulerian digraph, second neighborhood conjecture, cycle decomposition, cycle intersection graph.

Mathematics Subject Classification: 05C45, 05C12, 05C20.

Full text (pdf)

1. J. Bang-Jensen, G.Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media, 2008.
2. B. Bollobas, Graph Theory: An Introductory Course, vol. 63., Springer Science & Business Media, 2012.
3. M. Cary, Cycle intersection graphs and minimum decycling sets of even graphs, arXiv preprint arXiv:1810.04252 (2018).
4. G. Chen, J. Shen, R. Yuster, Second neighborhood via first neighborhood in digraphs, Ann. Comb. 7 (2003) 1, 15-20.
5. Z. Cohn, A. Godbole, E. Wright Harkness, Y. Zhang, The number of seymour vertices in random tournaments and digraphs, Graphs Combin. 32 (2016) 5, 1805-1816.
6. S. Dara, M.C. Francis, D. Jacob, N. Narayanan, The second neighborhood conjecture for some special classes of graphs, arXiv preprint arXiv:1808.02247 (2018).
7. N. Dean, B.J. Latka, Squaring the tournament-an open problem, Congr. Numer. (1995), 73-80.
8. D. Fidler, R. Yuster, Remarks on the second neighborhood problem, J. Graph Theory 55 (2007) 3, 208-220.
9. D.C. Fisher, Squaring a tournament: a proof of dean's conjecture, J. Graph Theory 23 (1996) 1, 43-48.
10. S. Ghazal, Seymour's second neighborhood conjecture for tournaments missing a generalized star, J. Graph Theory 71 (2012) 1, 89-94.
11. F. Havet, S. Thomassé, Median orders of tournaments: A tool for the second neighborhood problem and sumner's conjecture, J. Graph Theory 35 (2000) 4, 244-256.
12. Y. Kaneko, S. Locke, The minimum degree approach for Paul Seymour's distance 2 conjecture, Congr. Numer. 148 (2001), 201-206.
13. S. Kozerenko, On expansive and anti-expansive tree maps, Opuscula Math. 38 (2018) 3, 379-393.
14. R.J. Li, B. Sheng, The second neighbourhood for quasi-transitive oriented graphs, Acta Math. Sin. (Engl. Ser.) 34 (2018) 9, 1391-1402.
15. T. Seacrest, Seymour's second neighborhood conjecture for subsets of vertices, arXiv preprint arXiv:1808.06293 (2018).
16. B.D. Sullivan, A summary of results and problems related to the Caccetta-Häggkvist conjecture, arXiv preprint, 2006.
17. C.-Q. Zhang, Circuit Double Cover of Graphs, Cambridge University Press, 2012.
• Communicated by Andrzej Żak.
• Revised: 2019-10-02.
• Accepted: 2019-10-04.
• Published online: 2019-11-22. 