The Number of Seymour Vertices in Random Tournaments and Digraphs

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 almo...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2016-09, Vol.32 (5), p.1805-1816
Main Authors: Cohn, Zachary, Godbole, Anant, Harkness, Elizabeth Wright, Zhang, Yiguang
Format: Article
Language:English
Subjects:
Combinatorics
Engineering Design
Mathematics
Mathematics and Statistics
Original Paper
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-015-1672-9