×

Seymour’s second neighborhood conjecture for 5-anti-transitive oriented graphs. (English) Zbl 1447.05114

Summary: Let \( k \geq 2\) be an integer. A digraph \(D = ( V , E )\) is \(k\)-anti-transitive if for every pair of vertices \(u , v \in V\), the existence of a directed path of length \(k\) from \(u\) to \(v\) implies that \(( u , v ) \notin E\). Under this definition, digraphs without transitive triangles are 2-anti-transitive digraphs. In this paper, we prove that Seymour’s second neighborhood conjecture (SSNC) holds for 5-anti-transitive oriented graphs and, as a consequence, it holds for every oriented graph whose underlining graph contains no cycle of length 6. SSNC asserts that every oriented finite simple graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood.

MSC:

05C38 Paths and cycles
05C12 Distance in graphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brantner, J.; Brockman, G.; Kay, B.; Snively, E., Contributions to Seymour’s second neighborhood conjecture, Involve, 2, 4, 385-393 (2009) · Zbl 1194.05049
[2] M. Daamouch, Seymour’s second neighborhood conjecture for m-free, k-transitive, k-anti-transitive digraphs and some approaches, submitted for publication.
[3] Daamouch, M., Seymour’s second neighborhood conjecture for some oriented graphs with no sink, Discrete Math. Lett., 4, 19-22 (2020)
[4] Fidler, D.; Yuster, R., Remarks on the second neighborhood problem, J. Graph Theory, 55, 3, 208-220 (2007) · Zbl 1122.05040
[5] Fisher, D., Squaring a tournament: a proof of Dean’s conjecture, J. Graph Theory, 23, 1, 43-48 (1996) · Zbl 0857.05042
[6] Galeana-Sánchez, H.; Hernández-Cruz, C., \(k\)-Kernels in \(k\)-transitive and \(k\)-quasi-transitive digraphs, Discrete Math., 312, 16, 2522-2530 (2012) · Zbl 1246.05067
[7] García-Vásquez, P. R.; Hernández-Cruz, C., Some results on 4-transitive digraphs, Discuss. Math. Graph Theory, 37, 1, 117-129 (2017) · Zbl 1354.05058
[8] Ghazal, S., Seymour’s second neighborhood conjecture for tournaments missing a generalized star, J. Graph Theory, 71, 1, 89-94 (2012) · Zbl 1248.05077
[9] Ghazal, S., A contribution to the second neighborhood problem, Graphs Combin., 29, 5, 1365-1375 (2013) · Zbl 1272.05064
[10] Ghazal, S., A remark on the second neighborhood conjecture, Electron. J. Graph Theory Appl., 3, 2, 182-190 (2015)
[11] G. Gutin, R. Li, Seymour’s second neighbourhood conjecture for quasi-transitive oriented graphs, https://arxiv.org/abs/1704.01389v1.
[12] Havet, F.; Thomassé, S., Median orders of tournaments: a tool for the second neighborhood problem and Sumner’s conjecture, J. Graph Theory, 35, 4, 244-256 (2000) · Zbl 0969.05029
[13] Kaneko, Y.; Locke, S. C., The minimum degree approach for Paul Seymour’s distance 2 conjecture, Congr. Numer., 148, 201-206 (2001) · Zbl 0996.05042
[14] Liang, H.; Xu, J.-M., On Seymour’s second neighborhood conjecture of \(m\)-free digraphs, Discrete Math., 340, 8, 1944-1949 (2017) · Zbl 1362.05053
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.