zbMATH — the first resource for mathematics

The number of Seymour vertices in random tournaments and digraphs. (English) Zbl 1351.05202
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.

05C80 Random graphs (graph-theoretic aspects)
05C20 Directed graphs (digraphs), tournaments
05C12 Distance in graphs
Full Text: DOI arXiv
[1] Alon, N., Spencer, J.: The Probabilistic Method. Wiley, New York (1992) · Zbl 0767.05001
[2] Caccetta, L; Häggkvist, R, On minimal digraphs with given girth, Congress. Numer., 21, 181-187, (1978) · Zbl 0406.05033
[3] Chen, G; Shen, J; Yuster, R, Second neighborhood via first neighborhood in digraphs, Ann. Comb., 7, 15-20, (2003) · Zbl 1017.05057
[4] Chung, F., Lu, L.: Complex Graphs and Networks. American Mathematical Society, Providence (2006) · Zbl 1114.90071
[5] Fisher, DC, Squaring a tournament: a proof of dean’s conjecture, J. Graph Theory, 23, 43-48, (1996) · Zbl 0857.05042
[6] Kaneko, Y; Locke, S, The minimum degree approach for seymour’s distance 2 conjecture, Congress. Numer., 148, 201-206, (2001) · Zbl 0996.05042
[7] Steele, J.M.: Probability Theory and Combinatorial Optimization. SIAM, Philadelphia (1997) · Zbl 0916.90233
[8] West, D.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Upper Saddle River (2001)
[9] http://www.math.uiuc.edu/ west/openp/2ndnbhd.html
[10] http://www.math.uiuc.edu/ west/openp/cacchagg.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.