The number of Seymour vertices in random tournaments and digraphs

DOI10.1007/S00373-015-1672-9MaRDI QIDQ343729zbMATH OpenOpenAlexFDO

Authors Zachary Cohn, Elizabeth Wright Harkness, Yiguang Zhang, Anant P. Godbole

Publication date 29 November 2016

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

digraphtournamentSeymour's conjecture

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Random graphs (graph-theoretic aspects) (05C80) Distance in graphs (05C12)

Abstract: Seymour's distance two conjecture states that in any digraph there exists a vertex (a "Seymour vertex") that has at least as many neighbors at distance two as it does at distance one. We explore the validity of probabilistic statements along lines suggested by Seymour's conjecture, proving that almost surely there are a "large" number of Seymour vertices in random tournaments and "even more" in general random digraphs.

Recommendations

• Seymour's second neighborhood conjecture for tournaments missing a generalized star
• scientific article; zbMATH DE number 1743979
• Seymour's second neighborhood conjecture for orientations of (pseudo)random graphs
• On the second neighborhood conjecture
• Seymour vertices in a quasi-transitive oriented graph

Cites work

• scientific article; zbMATH DE number 53883 (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?)
• scientific article; zbMATH DE number 964350 (Why is no real title available?)
• Complex graphs and networks
• Second neighborhood via first neighborhood in digraphs

Cited in

(9)

• The second neighbourhood for quasi-transitive oriented graphs
• Vertices with the second neighborhood property in Eulerian digraphs
• Seymour's second neighborhood conjecture for orientations of (pseudo)random graphs
• A note on Seymour's second neighborhood conjecture
• Tournaments and Semicomplete Digraphs
• Second neighborhood via probabilistic argument
• The second out-neighborhood for local tournaments
• On Seymour's second neighborhood conjecture of \(m\)-free digraphs
• The second neighbourhood for bipartite tournaments

This page was built for publication: The number of Seymour vertices in random tournaments and digraphs

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