Geodesic
On the connectivity of configuration graphs
Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 114-122
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We consider configuration graphs with vertex degrees being independent identically distributed random variables. The distribution of these variables satisfies only relatively weak constraints on the probabilities of large values of degrees. For the case when the number of vertices tends to infinity, the conditions are found under which the graph is asymptotically almost surely connected. We also give estimates of the rate of convergence to zero of the probability that the graph is not connected.
Mots-clés : configuration graph
Keywords: random vertex degrees, graph connectivity. 
@article{DM_2019_31_2_a8,
     author = {Yu. L. Pavlov},
     title = {On the connectivity of configuration graphs},
     journal = {Diskretnaya Matematika},
     pages = {114--122},
     year = {2019},
     volume = {31},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_2019_31_2_a8/}
}
TY  - JOUR
AU  - Yu. L. Pavlov
TI  - On the connectivity of configuration graphs
JO  - Diskretnaya Matematika
PY  - 2019
SP  - 114
EP  - 122
VL  - 31
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DM_2019_31_2_a8/
LA  - ru
ID  - DM_2019_31_2_a8
ER  - 
%0 Journal Article
%A Yu. L. Pavlov
%T On the connectivity of configuration graphs
%J Diskretnaya Matematika
%D 2019
%P 114-122
%V 31
%N 2
%U http://geodesic.mathdoc.fr/item/DM_2019_31_2_a8/
%G ru
%F DM_2019_31_2_a8
Yu. L. Pavlov. On the connectivity of configuration graphs. Diskretnaya Matematika, Tome 31 (2019) no. 2, pp. 114-122. http://geodesic.mathdoc.fr/item/DM_2019_31_2_a8/

[1] Hofstad R., Random graphs and complex networks, v. 1, Cambridge Univ. Press, Cambridge, 2017, 321 pp. | MR | Zbl

[2] Faloutsos C., Faloutsos P., Faloutsos M., “On power-law relationships of the Internet topology”, Computer Communications Rev., 29 (1999), 251–262 | DOI

[3] Bollobas B., “A probabilistic proof of an asymptotic formula for the number of labelled regular graphs”, European J.Combin., 1:4 (1980), 311–316 | DOI | MR | Zbl

[4] Reittu H., Norros I., “On the power-law random graph model of massive data networks”, Performance Evalation, 55:1-2 (2004), 3–23 | DOI

[5] Durrett R., Random graph dynamics, Cambridge Univ. Press, Cambridge, 2007, 212 pp. | MR | Zbl

[6] Leri M., Pavlov Yu.,, “Power-law random graphs robustness: link saving and forest fire model”, Austrian J. Stat., 43:4 (2014), 229–236 | DOI

[7] Pavlov Yu. L., Cheplyukova I. A., “Sluchainye grafy Internet-tipa i obobschennaya skhema razmescheniya”, Diskretnaya matematika, 20:3 (2008), 3–18 | DOI | Zbl

[8] Pavlov Yu. L., “On the limit distributions of the vertex degrees of conditional Internet graphs”, Discrete Math. Appl., 19:4 (2009), 349–359 | DOI | DOI | MR | Zbl

[9] Pavlov Yu. L., Khvorostyanskaya E. V., “On the limit distributions of the degrees of vertices in configuration graphs with a bounded number of edges”, Sb. Math., 207:3 (2016), 400–417 | DOI | DOI | MR | Zbl

[10] Pavlov Yu. L., “Conditional configuration graphs with discrete power-law distribution of vertex degrees”, Sb. Math., 209:2 (2018), 258–275 | DOI | DOI | MR | Zbl

[11] Hofstad R., Random graphs and complex networks, v. 2, 2018, 314 pp. https://www.win.tue.nl/~rhofstad/NotesRGCII.pdf

[12] Ibragimov I. A., Linnik Yu. V., Independent and stationary sequences of random variables, Wolters-Noordhof, Groningen, 1971, 443 pp. | MR | MR | Zbl

[13] Lukacs E., Characteristic function, Griffin, London, 1970, 350 pp. | MR