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.
2023
Almost-2-regular random graphs / Federico, Lorenzo. - In: TEH AUSTRALASIAN JOURNAL OF COMBINATORICS. - ISSN 1034-4942. - 86:1(2023), pp. 76-96.
File in questo prodotto:
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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11385/228458
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
  • OpenAlex ND
social impact