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
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.
- J. Bang-Jensen, G.Z. Gutin, Digraphs: Theory, Algorithms and Applications, Springer Science & Business Media, 2008.
- B. Bollobas, Graph Theory: An Introductory Course, vol. 63., Springer Science & Business Media, 2012.
- M. Cary, Cycle intersection graphs and minimum decycling sets of even graphs, arXiv preprint arXiv:1810.04252 (2018).
- G. Chen, J. Shen, R. Yuster, Second neighborhood via first neighborhood in digraphs, Ann. Comb. 7 (2003) 1, 15-20.
- 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.
- 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).
- N. Dean, B.J. Latka, Squaring the tournament-an open problem, Congr. Numer. (1995), 73-80.
- D. Fidler, R. Yuster, Remarks on the second neighborhood problem, J. Graph Theory 55 (2007) 3, 208-220.
- D.C. Fisher, Squaring a tournament: a proof of dean's conjecture, J. Graph Theory 23 (1996) 1, 43-48.
- S. Ghazal, Seymour's second neighborhood conjecture for tournaments missing a generalized star, J. Graph Theory 71 (2012) 1, 89-94.
- 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.
- Y. Kaneko, S. Locke, The minimum degree approach for Paul Seymour's distance 2 conjecture, Congr. Numer. 148 (2001), 201-206.
- S. Kozerenko, On expansive and anti-expansive tree maps, Opuscula Math. 38 (2018) 3, 379-393.
- R.J. Li, B. Sheng, The second neighbourhood for quasi-transitive oriented graphs, Acta Math. Sin. (Engl. Ser.) 34 (2018) 9, 1391-1402.
- T. Seacrest, Seymour's second neighborhood conjecture for subsets of vertices, arXiv preprint arXiv:1808.06293 (2018).
- B.D. Sullivan, A summary of results and problems related to the Caccetta-Häggkvist conjecture, arXiv preprint, 2006.
- C.-Q. Zhang, Circuit Double Cover of Graphs, Cambridge University Press, 2012.
- Michael Cary
https://orcid.org/0000-0002-6984-6712- West Virgnia University, Morgantown, WV, USA
- Communicated by Andrzej Żak.
- Received: 2019-04-19.
- Revised: 2019-10-02.
- Accepted: 2019-10-04.
- Published online: 2019-11-22.
