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.
Federico, Lorenzo. (2023). Almost-2-regular random graphs. TEH AUSTRALASIAN JOURNAL OF COMBINATORICS, (ISSN: 1034-4942), 86:1, 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.
