Premium
On the connectivity of a random interval graph
Author(s) -
Godehardt Erhard,
Jaworski Jerzy
Publication year - 1996
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/(sici)1098-2418(199608/09)9:1/2<137::aid-rsa9>3.0.co;2-y
Subject(s) - random graph , mathematics , poisson distribution , combinatorics , interval (graph theory) , discrete mathematics , unit interval , random variable , binomial (polynomial) , binomial distribution , graph , statistics
We study a uniform model IG n,d for random interval graphs on the unit interval. We derive exact results and limit theorems for the distribution of random variables related to the connectivity of this random interval graph. While having the same threshold function for some properties like the Poisson approximation for the number of isolated vertices, our results show that the standard binomial model G n,p of random graphs and IG n,d differ in many aspects. © 1996 John Wiley & Sons, Inc.