Premium
Asymptotic properties of labeled connected graphs
Author(s) -
Bender Edward A.,
Canfield E. Rodney,
McKay Brendan D.
Publication year - 1992
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.3240030208
Subject(s) - combinatorics , mathematics , vertex (graph theory) , random graph , asymptotic formula , discrete mathematics , asymptotic expansion , graph , mathematical analysis
We prove various properties of C ( n, q ), the set of n ‐vertex q ‐edge labeled connected graphs. The domain of validity of the asymptotic formula of Erdös and Rényi for | C ( n, q )| is extended and the formula is seen to be the first term of an asymptotic expansion. The same is done for Wright's asymptotic formula. We study the number of edges in a random connected graph in the random edge model n,p . For certain ranges of n and q , we determine the probability that a random edge (resp. vertex) of a random graph in C ( n, q ) is a bridge (resp. cut vertex). We also study the degrees of random vertices.