No Detail Found!

Seymour's second neighborhood conjecture for some oriented graphs with no sink

Author(s)
Moussa Daamouch Lebanese University, Faculty of Sciences I,Beirut,Lebanon
Abstract
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 k 2 1 has at least two Seymour vertices, and we deduce that the SNC holds for every k-transitive oriented graph with k 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.
Publication Details
Page(s) 19-22
DOI DOI not available
Published Journal: Discrete Mathematics Letters, Volume: 4, Issue: 0, Year: 2020

Request the full text from PASTIC

Keywords
sink, k-transitive digraph, 3-quasi-transitive digraph, Seymour's second neighborhood conjecture
References
Daamouch M. . .Seymour's second neighborhood conjecture for m-free, k-transitive, k-anti-transitive digraphs and some approaches. , : .
Dara S.,Francis M. C.,Jacob D.,Narayanan N. .2019 .Extending some results on the second neighborhood conjecture. , : .
Dean N.,Latka B. J. .1995 .Squaring the tournament-an open problem. Congr. Numer, 109 : 73-80.
Fidler D.,Yuster R. .2007 .Remarks on the second neighborhood problem. J. Graph Theory, 55 : 208-220.
Fisher D. .1996 .Squaring a tournament: a proof of Dean's conjecture. J. Graph Theory, 23 : 43-48.
Galeana-S H. .2010 .a´nchez, I. A. Goldfeder, I. Urritia, On the structure of strong 3-quasi-transitive digraphs. , 310 : 2495-2498.
Galeana-Sa H.,Hern C.,Cruz C.,Bang-Jensen C. .2018 .Quasi-transitive Digraphs and Their Extensions. Classes of Directed Graphs, : 341-404.
Galeana-S H. .2012 .a´nchez, C. Hern a´ndez-Cruz, k-kernels in k-transitive and k-quasi-transitive digraphs. , 312 : 2522-2530.
Garc P. R.,Cruz P. R. .2017 .Some results on 4-transitive digraphs. Discuss. Math. Graph Theory, 37 : 117-129.
Ghazal S. .2012 .Seymour's second neighborhood conjecture for tournaments missing a generalized star. J. Graph Theory, 71 : 89-94.
Ghazal S. .2013 .A contribution to the second neighborhood problem. Graphs Combin, 29 : 1365-1375.
Ghazal S. .2015 .A remark on the second neighborhood conjecture. Electron. J. Graph Theory Appl, 3 : 182-190.
Gutin G.,Li R. .2017 .Seymour's second neighbourhood conjecture for quasi-transitive oriented graphs. arXiv: 1704.01389v2, : .
Havet F.,S. F. .2000 .Thomasse´, Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture. J. Graph Theory, 35 : 244-256.
Hern C.,Cruz J. J.,Montellano-Ballesteros J. J. .2014 .Some remarks on the structure of strong k-transitive digraphs. Discuss. Math. Graph Theory, 34 : 651-672.
Kaneko Y.,Locke S. C. .2001 .The minimum degree approach for Paul Seymour's distance 2 conjecture, Congr. , 148 : 201-206.
Li R.,Sheng B. .2019 .The second neighborhood for bipartite tournaments. Discuss. Math. Graph Theory, 39 : 555-565.
0

Citations

0

Downloads

21

Views