Premium
Minors in random regular graphs
Author(s) -
Fountoulakis Nikolaos,
Kühn Daniela,
Osthus Deryk
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20285
Subject(s) - combinatorics , mathematics , corollary , random regular graph , graph , graph minor , conjecture , distance regular graph , regular graph , discrete mathematics , minor (academic) , graph power , 1 planar graph , line graph , political science , law
Abstract We show that there is a constant c so that for fixed r ≥ 3 a.a.s. an r ‐regular graph on n vertices contains a complete graph on $ c\sqrt{n} $ vertices as a minor. This confirms a conjecture of Markström (Ars Combinatoria 70 (2004) 289–295). Since any minor of an r ‐regular graph on n vertices has at most r n /2 edges, our bound is clearly best possible up to the value of the constant c . As a corollary, we also obtain the likely order of magnitude of the largest complete minor in a random graph G n , p during the phase transition (i.e., when p n → 1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009