We study a special case of the configuration model, in which almost all the vertices of the graph have degree 2. We show that the graph has a very peculiar and interesting behaviour; in particular, when the graph is made up of a vast majority of vertices of degree 2 and a vanishing proportion of vertices of higher degree, the giant component contains n(1 − o(1)) vertices, but the second component can still grow as a power of n. On the other hand, when almost all the vertices have degree 2, except for o(n) which have degree 1, there is no component of linear size.
Almost-2-regular random graphs / Federico, Lorenzo. - In: TEH AUSTRALASIAN JOURNAL OF COMBINATORICS. - ISSN 1034-4942. - 86:1(2023), pp. 76-96.
Almost-2-regular random graphs
Federico L.
2023
Abstract
We study a special case of the configuration model, in which almost all the vertices of the graph have degree 2. We show that the graph has a very peculiar and interesting behaviour; in particular, when the graph is made up of a vast majority of vertices of degree 2 and a vanishing proportion of vertices of higher degree, the giant component contains n(1 − o(1)) vertices, but the second component can still grow as a power of n. On the other hand, when almost all the vertices have degree 2, except for o(n) which have degree 1, there is no component of linear size.
| File | Dimensione | Formato | |
|---|---|---|---|
|
ajc_v86_p076.pdf
Open Access
Tipologia:
Versione dell'editore
Licenza:
Creative commons
Dimensione
398.93 kB
Formato
Adobe PDF
|
398.93 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
