The number of Seymour vertices in random tournaments and digraphs

DOI10.1007/S00373-015-1672-9zbMATH Open1351.05202arXiv1502.04061OpenAlexW2113084356MaRDI QIDQ343729FDOQ343729

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)

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.

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

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

zbMATH Keywords

digraphtournamentSeymour's conjecture

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Complex graphs and networks
• Title not available (Why is that?)
• Second neighborhood via first neighborhood in digraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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)