Vertices with the second neighborhood property in Eulerian digraphs

• Autorzy: Cary Michael

Identyfikatory

DOI

10.7494/OpMath.2019.39.6.765

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Eulerian digraph; second neighborhood conjecture; cycle decomposition; cycle intersection graph

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2019
• Tom: Vol. 39, no. 6
• Strony: 765--772
• Opis fizyczny: Bibliogr, 17 poz.

Twórcy

autor

Cary Michael

• West Virgnia University, Morgantown, WV, USA

Bibliografia

• [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 seyrnour 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 tournarnent-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. Thomasse, 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-Haggkvist conjecture, arXiv preprint, 2006.
• [17] C.-Q. Zhang, Circuit Double Cover of Graphs, Cambridge University Press, 2012.