Projects per year
Abstract
We show that there is a constant c so that for fixed r >= 3 a.a.s. an rregular graph on n vertices contains a complete graph on c root n vertices as a minor. This confirms a conjecture of Markstrom (Ars Combinatoria 70 (2004) 289295). Since any minor of an rregular graph on n vertices has at most m/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,,,p during the phase transition (i.e., when pn > 1). (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 444463, 2009
Original language  English 

Pages (fromto)  444463 
Number of pages  20 
Journal  Random Structures and Algorithms 
Volume  35 
Issue number  4 
DOIs  
Publication status  Published  1 Dec 2009 
Keywords
 Hadwiger number
 random regular graphs
 graph minors
Fingerprint
Dive into the research topics of 'Minors in Random Regular Graphs'. Together they form a unique fingerprint.Projects
 1 Finished

Probabilistic Methods in Graph Theory
Engineering & Physical Science Research Council
26/04/06 → 25/01/09
Project: Research Councils