PL EN

Preferencje
Język
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo

## Discussiones Mathematicae Graph Theory

2008 | 28 | 3 | 511-533
Tytuł artykułu

### The sizes of components in random circle graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
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.
Słowa kluczowe
EN
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
Numer
Strony
511-533
Opis fizyczny
Daty
wydano
2008
otrzymano
2008-02-18
poprawiono
2008-04-04
zaakceptowano
2008-04-07
Twórcy
autor
• Shahid Beheshti University, Department of Statistics, Evin, Tehran, Iran
Bibliografia
• [1] L. Fatto and A.G. Konheim, The random division of an interval and the random covering of a circle, SIAM Review 4 (1962) 211-222, doi: 10.1137/1004058.
• [2] E. Godehardt and J. Jaworski, On the connectivity of a random interval graphs, Random Structures and Algorithms 9 (1996) 137-161, doi: 10.1002/(SICI)1098-2418(199608/09)9:1/2<137::AID-RSA9>3.0.CO;2-Y
• [3] L. Holst and J. Husler, On the random coverage of the circle, J. Appl. Prob. 21 (1984) 558-566, doi: 10.2307/3213617.
• [4] T. Huillet, Random covering of the circle: the size of the connected components, Adv. in Appl. Probab. 35 (2003) 563-582, doi: 10.1239/aap/1059486818.
• [5] H. Maehara, On the intersection graph of random arcs on a circle, Random Graphs' 87 (1990) 159-173.
• [6] M. Penrose, Random Geometric Graphs (Oxford Studies in Probability, 2003), doi: 10.1093/acprof:oso/9780198506263.001.0001.
• [7] A.F. Siegel, Random arcs on the circle, J. Appl. Prob. 15 (1978) 774-789, doi: 10.2307/3213433.
• [8] H. Solomon, Geometric Probability (Society for Industrial and Applied Mathematics, Philadelphia, 1976).
• [9] F.W. Steutel, Random division of an interval, Statistica Neerlandica 21 (1967) 231-244, doi: 10.1111/j.1467-9574.1967.tb00561.x.
• [10] W.L. Stevens, Solution to a geometrical problem in probability, Ann. Eugenics 9 (1939) 315-320, doi: 10.1111/j.1469-1809.1939.tb02216.x.
Typ dokumentu
Bibliografia
Identyfikatory