Hamilton cycles and perfect matchings in the KPKVB model

STOCHASTIC PROCESSES AND THEIR APPLICATIONS

卷:131

Article

Fountoulakis, Nikolaos¹  Mitsche, Dieter²  Muller, Tobias³  Schepers, Markus³ 

[1] Univ Birmingham, Sch Math, Birmingham, W Midlands, England

[2] Univ Lyon, Univ Jean Monnet, Inst Camille Jordan, Lyon, France

[3] Univ Groningen, Benoulli Inst, Groningen, Netherlands

关键词: Hamilton cycle;    Perfect matching;    Hyperbolic random graph;    Poisson process;    Randomized algorithm;    Tiling;   

DOI  :  10.1016/j.spa.2020.09.012

来源: Elsevier

【 摘 要 】

In this paper we consider the existence of Hamilton cycles and perfect matchings in a random graph model proposed by Krioukov et al. in 2010. In this model, nodes are chosen randomly inside a disk in the hyperbolic plane and two nodes are connected if they are at most a certain hyperbolic distance from each other. It has been previously shown that this model has various properties associated with complex networks, including a power-law degree distribution, short distances and a non-vanishing clustering coefficient. The model is specified using three parameters: the number of nodes n, which we think of as going to infinity, and alpha, nu > 0, which we think of as constant. Roughly speaking alpha controls the power law exponent of the degree sequence and nu the average degree. Here we show that for every alpha < 1/2 and nu = nu(alpha) sufficiently small, the model does not contain a perfect matching with high probability, whereas for every alpha < 1/2 and nu = nu(alpha) sufficiently large, the model contains a Hamilton cycle with high probability. (C) 2020 Elsevier B.Y. All rights reserved.

【 授权许可】

Free