Premium
Random cubic planar graphs
Author(s) -
Bodirsky Manuel,
Kang Mihyun,
Löffler Mike,
McDiarmid Colin
Publication year - 2006
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.20149
Subject(s) - planar , combinatorics , mathematics , random graph , cubic graph , planar graph , random regular graph , struct , cubic form , probabilistic logic , discrete mathematics , cubic crystal system , graph , chordal graph , 1 planar graph , computer science , physics , statistics , condensed matter physics , line graph , voltage graph , programming language , computer graphics (images)
We show that the number of labeled cubic planar graphs on n vertices with n even is asymptotically α n −7/2 ρ − n n !, where ρ −1 ≐ 3.13259 and α are analytic constants. We show also that the chromatic number of a random cubic planar graph that is chosen uniformly at random among all the labeled cubic planar graphs on n vertices is three with probability tending to e −ρ 4 /4!≐ 0.999568 and four with probability tending to 1 − e −ρ 4 /4!as n → ∞ with n even. The proof given combines generating function techniques with probabilistic arguments. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom