Strong $k$-transitive oriented graphs with large minimum degree

Articles in Press

Document Type : Original paper

Author

KALMA Laboratory, Department of Mathematics, Faculty of Sciences I, Lebanese University, Beirut, Lebanon

Abstract

A digraph $D=(V,E)$ is $k$-transitive if for any directed $uv$-path of length $k$, we have $(u,v) \in E$. In this paper, we study the structure of strong $k$-transitive oriented graphs having large minimum in- or out-degree. We show that such oriented graphs are \emph{extended cycles}. As a consequence, we prove that Seymour's Second Neighborhood Conjecture (SSNC) holds for $k$-transitive oriented graphs for $k \leq 11$. Also we confirm Bermond--Thomassen Conjecture for $k$-transitive oriented graphs for $k \leq 11$. A characterization of $k$-transitive oriented graphs having a hamiltonian cycle for $k \leq 6$ is obtained immediately.

Keywords

Main Subjects

References

[1] D. Al-Mniny and S. Ghazal, The second neighborhood conjecture for oriented graphs missing a $\{C_4, \overline{C_4}, S_3, {\rm chair\; and}\;  \overline{{\rm chair}}\}$-free graph, Australas. J. Comb. 81 (2021), no. 1, 58–88.
[2] Y. Bai, B. Li, and H. Li, Vertex-disjoint cycles in bipartite tournaments, Discrete Math. 338 (2015), no. 8, 1307–1309. https://doi.org/10.1016/j.disc.2015.02.012
[3] J. Bang-Jensen, S. Bessy, and S. Thomassen, Disjoint 3-cycles in tournaments: A proof of the Bermond–Thomassen conjecture for tournaments, J. Graph Theory 75 (2014), no. 3, 284–302.  https://doi.org/10.1002/jgt.21740
[4] J.C. Bermond and C. Thomassen, Cycles in digraphs– a survey, J. Graph Theory 5 (1981), no. 1, 1–43. https://doi.org/10.1002/jgt.3190050102
[5] M. Cary, Vertices with the second neighborhood property in Eulerian digraphs, Opuscula Math. 39 (2019), no. 6, 765–772.  https://doi.org/10.7494/OpMath.2019.39.6.765
[6] M. Daamouch, Seymour’s second neighborhood conjecture for 5-anti-transitive oriented graphs, Discrete Appl. Math. 285 (2020), 454–457.  https://doi.org/10.1016/j.dam.2020.06.011
[7] M. Daamouch, Seymour’s second neighborhood conjecture for some oriented graphs with no sink, Discrete Math. Lett. 4 (2020), 19–22.
[8] M. Daamouch, Seymour’s second neighborhood conjecture for $m$-free, $k$-transitive, $k$-anti-transitive digraphs and some approaches, Discrete Appl. Math. 304 (2021), 332–341.  https://doi.org/10.1016/j.dam.2021.08.011
[9] S. Dara, C.F. Mathew, J. Dalu, and N. Narayanan, Extending some results on the second neighborhood conjecture, Discrete Appl. Math. 311 (2022), 1–17.  https://doi.org/10.1016/j.dam.2021.12.034
[10] D. Fidler and R. Yuster, Remarks on the second neighborhood problem, J. Graph Theory 55 (2007), no. 3, 208–220. https://doi.org/10.1002/jgt.20229
[11] D.C. Fisher, Squaring a tournament: A proof of Dean’s conjecture, J. Graph Theory 23 (1996), no. 1, 43–48.
[12] H. Galeana-Sánchez and C. Hernández-Cruz, Quasi-transitive digraphs and their extensions, Classes of Directed Graphs, Springer, 2018, pp. 341–404.
[13] P.R. García-Vázquez and C. Hernández-Cruz, Some results on 4-transitive digraphs, Discuss. Math. Graph Theory 37 (2017), no. 1, 117–129. http://doi.org/10.7151/dmgt.1922
[14] S. Ghazal, Seymour’s second neighborhood conjecture for tournaments missing a generalized star, J. Graph Theory 71 (2012), no. 1, 89–94. https://doi.org/10.1002/jgt.20634
[15] S. Ghazal, A contribution to the second neighborhood problem, Graphs Combin. 29 (2013), no. 5, 1365–1375. https://doi.org/10.1007/s00373-012-1192-9
[16] Z.R. Hassan, I.F. Khan, M.I. Poshni, and M. Shabbir, Seymour’s second neighborhood conjecture for 6-antitransitive digraphs, Discrete Appl. Math. 292 (2021), 59–63.  https://doi.org/10.1016/j.dam.2020.12.026
[17] C. Hernández-Cruz, 3-transitive digraphs, Discuss. Math. Graph Theory 32 (2012), no. 2, 205–219. http://doi.org/10.7151/dmgt.1613
[18] C. Hernández-Cruz, 4-transitive digraphs I: The structure of strong 4-transitive digraphs, Discuss. Math. Graph Theory 33 (2013), no. 2, 247–260.  http://doi.org/10.7151/dmgt.1645
[19] C. Hernández-Cruz and H. Galeana-Sánchez, k-kernels in k-transitive and $k$-quasi-transitive digraphs, Discrete Math. 312 (2012), no. 16, 2522–2530.  https://doi.org/10.1016/j.disc.2012.05.005
[20] C. Hernández-Cruz and J.J. Montellano-Ballesteros, Some remarks on the structure of strong $k$-transitive digraphs, Discuss. Math. Graph Theory 34 (2014), no. 4, 651–671.  http://doi.org/10.7151/dmgt.1765
[21] B. Jackson, Long paths and cycles in oriented graphs, J. Graph Theory 5 (1981), no. 2, 145–157. https://doi.org/10.1002/jgt.3190050204
[22] Y. Kaneko and S.C. Locke, The minimum degree approach for Paul Seymour’s distance 2 conjecture, Congr. Numer. 148 (2001), 201–206.
[23] R. Li and B. Sheng, The second neighbourhood for bipartite tournaments, Discuss. Math. Graph Theory 39 (2019), no. 2, 555–565.  http://doi.org/10.7151/dmgt.2018
[24] N. Lichiardopol, A. Pór, and J.S. Sereni, A step toward the Bermond–Thomassen conjecture about disjoint cycles in digraphs, SIAM J. Discrete Math. 23 (2009), no. 2, 979–992.  https://doi.org/10.1137/080715792
[25] C. Thomassen, Disjoint cycles in digraphs, Combinatorica 3 (1983), no. 3, 393–396. https://doi.org/10.1007/BF02579195
Communications in Combinatorics and Optimization

Articles in Press, Accepted Manuscript
Available Online from 16 February 2024

Files

Share

How to cite

Statistics