Geodesic
The sizes of components in random circle graphs
Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 511-533

Voir la notice de l'article provenant de la source Library of Science

We study random circle graphs which are generated by throwing n points (vertices) on the circle of unit circumference at random and joining them by an edge if the length of shorter arc between them is less than or equal to a given parameter d. We derive here some exact and asymptotic results on sizes (the numbers of vertices) of "typical" connected components for different ways of sampling them. By studying the joint distribution of the sizes of two components, we "go into" the structure of random circle graphs more deeply. As a corollary of one of our results we get the exact, closed formula for the expected value of the total length of all components of the random circle graph. Although the asymptotic distribution for this random characteristic is well known (see e.g. T. Huillet [4]), this surprisingly simple formula seems to be a new one.
Keywords: random interval graphs, geometric graphs, geometric probability 
@article{DMGT_2008_28_3_a10,
     author = {Imany-Nabiyyi, Ramin},
     title = {The sizes of components in random circle graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {511--533},
     publisher = {mathdoc},
     volume = {28},
     number = {3},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a10/}
}
TY  - JOUR
AU  - Imany-Nabiyyi, Ramin
TI  - The sizes of components in random circle graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2008
SP  - 511
EP  - 533
VL  - 28
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a10/
LA  - en
ID  - DMGT_2008_28_3_a10
ER  - 
%0 Journal Article
%A Imany-Nabiyyi, Ramin
%T The sizes of components in random circle graphs
%J Discussiones Mathematicae. Graph Theory
%D 2008
%P 511-533
%V 28
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a10/
%G en
%F DMGT_2008_28_3_a10
Imany-Nabiyyi, Ramin. The sizes of components in random circle graphs. Discussiones Mathematicae. Graph Theory, Tome 28 (2008) no. 3, pp. 511-533. http://geodesic.mathdoc.fr/item/DMGT_2008_28_3_a10/