ON THE CONNECTIVITY OF A RANDOM INTERVAL GRAPH

Authors
GODEHARDT E JAWORSKI J
Citation
E. Godehardt et J. Jaworski, ON THE CONNECTIVITY OF A RANDOM INTERVAL GRAPH, Random structures & algorithms, 9(1-2), 1996, pp. 137-161
Citations number
16
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
9
Issue
1-2
Year of publication
1996
Pages
137 - 161
Database
ISI
SICI code
1042-9832(1996)9:1-2<137:OTCOAR>2.0.ZU;2-L
Abstract
We study a uniform model SG(n,d) for random interval graphs on the uni t interval. We derive exact results and limit theorems for the distrib ution of random variables related to the connectivity of this random i nterval graph. While having the same threshold function for some prope rties like the Poisson approximation for the number of isolated vertic es, our results show that the standard binomial model G(n,p) of random graphs and SG(n,d) differ in many aspects. (C) 1996 John Wiley & Sons , Inc.