Extending some results on the second neighborhood conjecture

DOI10.1016/J.DAM.2021.12.034MaRDI QIDQ2078833zbMATH OpenOpenAlexWikidataFDO

Authors Suresh Dara, Mathew C. Francis, Dalu Jacob, N. Narayanan

Publication date 4 March 2022

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1808.02247

zbMATH Keywords

median orders of tournamentsoriented graphssecond neighborhood conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Structural characterization of families of graphs (05C75)

Abstract: A vertex in a directed graph is said to have a large second neighborhood if it has at least as many second out-neighbors as out-neighbors. The Second Neighborhood Conjecture, first stated by Seymour, asserts that there is a vertex having a large second neighborhood in every oriented graph (a directed graph without loops or digons). We prove that oriented graphs whose missing edges can be partitioned into a (possibly empty) matching and a (possibly empty) star satisfy this conjecture. This generalizes a result of Fidler and Yuster. An implication of our result is that every oriented graph without a sink and whose missing edges form a (possibly empty) matching has at least two vertices with large second neighborhoods. This is a strengthening of a theorem of Havet and Thomasse, who showed that the same holds for tournaments without a sink. Moreover, we also show that the conjecture is true for oriented graphs whose vertex set can be partitioned into an independent set and a 2-degenerate graph.

Recommendations

• A contribution to the second neighborhood problem
• Remarks on the second neighborhood problem
• On the second neighborhood conjecture
• About the second neighborhood problem in tournaments missing disjoint stars
• The second out-neighborhood for local tournaments

Cites work

• A remark on the second neighborhood problem
• scientific article; zbMATH DE number 1185310 (Why is no real title available?)
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• scientific article; zbMATH DE number 1743979 (Why is no real title available?)
• scientific article; zbMATH DE number 927068 (Why is no real title available?)
• Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture
• On the second neighborhood conjecture of Seymour for regular digraphs with almost optimal connectivity
• Remarks on the second neighborhood problem
• Seymour's second neighborhood conjecture for tournaments missing a generalized star

Cited in

(11)

• The second neighbourhood for bipartite tournaments
• The second out-neighborhood for local tournaments
• A contribution to the second neighborhood problem
• About the second neighborhood problem in tournaments missing disjoint stars
• Remarks on the second neighborhood problem
• Seymour's second neighborhood conjecture for line digraph of digraph and its jump digraph
• Seymour's second neighborhood conjecture for some oriented graphs
• About the second neighborhood conjecture for tournaments missing two stars or disjoint paths
• Strong k-transitive oriented graphs with large minimum degree
• A note on the second neighborhood problem
• A note on the second neighborhood problem for k-anti-transitive digraphs with large girth

This page was built for publication: Extending some results on the second neighborhood conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2078833)