Premium
On the genus of a random graph
Author(s) -
Rödl Vojtěch,
Thomas Robin
Publication year - 1995
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.3240060102
Subject(s) - combinatorics , mathematics , random regular graph , graph , random graph , vertex (graph theory) , genus , discrete mathematics , line graph , biology , pathwidth , botany
Let p = p ( n ) be a function of n with 0< p <1. We consider the random graph model ( n, p ); that is, the probability space of simple graphs with vertex‐set {1, 2,…, n }, where two distinct vertices are adjacent with probability p . and for distinct pairs these events are mutually independent. Archdeacon and Grable have shown that if p 2 (1 − p 2 ) 8(log n ) 4 / n . then the (orientable) genus of a random graph in ( n, p ) is (1 + o (1)) pn 2 /12. We prove that for every integer i ⩾ 1, if n −i/ ( i + 1) « p « n −( i − 1)/ i . then the genus of a random graph in ( n, p ) is (1 + o (1)) i /4( i + 2) pn 2 . If p = cn −( i −1)/ o , where c is a constant, then the genus of a random graph in ( n, p ) is (1 + o (1)) g ( i, c, n ) pn 2 for some function g ( i, c, n ) with 1/12 ⩽ g ( i, c, n ) ⩽ 1. but for i > 1 we were unable to compute this function.