Opuscula Math. 39, no. 6 (2019), 765-772

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.
  • Received: 2019-04-19.
  • Revised: 2019-10-02.
  • Accepted: 2019-10-04.
  • Published online: 2019-11-22.
Opuscula Mathematica - cover

Cite this article as:
Michael Cary, Vertices with the second neighborhood property in Eulerian digraphs, Opuscula Math. 39, no. 6 (2019), 765-772, https://doi.org/10.7494/OpMath.2019.39.6.765

Download this article's citation as:
a .bib file (BibTeX),
a .ris file (RefMan),
a .enw file (EndNote)
or export to RefWorks.

In accordance with EU legislation we advise you this website uses cookies to allow us to see how the site is used. All data is anonymized.
All recent versions of popular browsers give users a level of control over cookies. Users can set their browsers to accept or reject all, or certain, cookies.