×

Seymour’s second neighborhood conjecture for some oriented graphs with no sink. (English) Zbl 1463.05218

Summary: Seymour’s Second Neighborhood Conjecture (SNC) asserts that every oriented graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is called a Seymour vertex. In this paper, we prove that every \(k\)-transitive oriented graph with minimum out-degree \(\delta \ge k-2 \ge 1\) has at least two Seymour vertices, and we deduce that the SNC holds for every \(k\)-transitive oriented graph with \(k \le 9\). We also prove that every 3-quasi-transitive oriented graph with no sink has at least two Seymour vertices, where sink is a vertex having out-degree zero.

MSC:

05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: Link

References:

[1] M. Daamouch, Seymour’s second neighborhood conjecture form-free,k-transitive,k-anti-transitive digraphs and some approaches, Submitted. · Zbl 1510.05091
[2] S. Dara, M. C. Francis, D. Jacob, N. Narayanan, Extending some results on the second neighborhood conjecture,arXiv: 1808.02247v2, 2019.
[3] N. Dean, B. J. Latka, Squaring the tournament-an open problem,Congr. Numer.109(1995) 73-80. · Zbl 0904.05034
[4] D. Fidler, R. Yuster, Remarks on the second neighborhood problem,J. Graph Theory55(2007) 208-220. · Zbl 1122.05040
[5] D. Fisher, Squaring a tournament: a proof of Dean’s conjecture,J. Graph Theory23(1996) 43-48. · Zbl 0857.05042
[6] H. Galeana-S ´anchez, I. A. Goldfeder, I. Urritia, On the structure of strong 3-quasi-transitive digraphs,Discrete Math.310(2010) 2495-2498. · Zbl 1213.05112
[7] H. Galeana-S ´anchez, C. Hern ´andez-Cruz, Quasi-transitive Digraphs and Their Extensions, In: J. Bang-Jensen, G. Gutin (Eds.),Classes of Directed Graphs, Springer, Cham, 2018, pp. 341-404. · Zbl 1407.05106
[8] H. Galeana-S ´anchez, C. Hern ´andez-Cruz,k-kernels ink-transitive andk-quasi-transitive digraphs,Discrete Math.312(2012) 2522-2530. · Zbl 1246.05067
[9] P. R. Garc´ıa-V ´asquez, C. Hern ´andez-Cruz, Some results on 4-transitive digraphs,Discuss. Math. Graph Theory37(2017) 117-129. · Zbl 1354.05058
[10] S. Ghazal, Seymour’s second neighborhood conjecture for tournaments missing a generalized star,J. Graph Theory71(2012) 89-94. · Zbl 1248.05077
[11] S. Ghazal, A contribution to the second neighborhood problem,Graphs Combin.29(2013) 1365-1375. · Zbl 1272.05064
[12] S. Ghazal, A remark on the second neighborhood conjecture,Electron. J. Graph Theory Appl.3(2015) 182-190. · Zbl 1467.05092
[13] G. Gutin, R. Li, Seymour’s second neighbourhood conjecture for quasi-transitive oriented graphs,arXiv: 1704.01389v2, 2017.
[14] F. Havet, S. Thomass´e, Median orders of tournaments: a tool for the second neighborhood problem and Sumner’s conjecture,J. Graph Theory35 (2000) 244-256. · Zbl 0969.05029
[15] C. Hern ´andez-Cruz, J. J. Montellano-Ballesteros, Some remarks on the structure of strongk-transitive digraphs,Discuss. Math. Graph Theory34 (2014) 651-672. · Zbl 1303.05075
[16] Y. Kaneko, S. C. Locke, The minimum degree approach for Paul Seymour’s distance 2 conjecture,Congr. Numer.148(2001) 201-206. · Zbl 0996.05042
[17] R. Li, B. Sheng, The second neighborhood for bipartite tournaments,Discuss. Math. Graph Theory39(2019) 555-565. · Zbl 1404.05069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.