RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 2016 Volume 28, Issue 2, Pages 58–70 (Mi dm1369)

This article is cited in 1 paper

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

Yu. L. Pavlov, E. V. Feklistova

Institute of Applied Mathematical Research of the Karelian Research Centre RAS, Petrozavodsk

Abstract: 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.

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

UDC: 519.175.4

Received: 09.06.2015

DOI: 10.4213/dm1369


 English version:
Discrete Mathematics and Applications, 2017, 27:4, 213–222

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025