On limit behavior of maximum vertex degree in a conditional configuration graph near critical points

Yu. L. Pavlov ; E. V. Feklistova

Diskretnaya Matematika, Tome 28 (2016) no. 2, pp. 58-70

Résumé

We consider configuration graphs with $N$ vertices. The degrees of vertices are independent identically distributed random variables having the power-law distribution with parameter $\tau>0$. There are two critical values of this parameter: $\tau=1$ and $\tau=2$. The properties of a graph change significantly when $\tau=\tau(N)$ passes these points as $N\to\infty$. Let $G_{N, n}$ be the subset of random graphs under the condition that sum of degrees of its vertices is equal to $n$. The limit theorem for the maximum vertex degree in $G_{N, n}$ as $N, n\to\infty$ and $\tau\to 1$ or $\tau\to 2$ is proved.

Détail

Keywords: random graph, configuration graph, maximum vertex degree, power-law distribution, critical point, limit theorems.