Hamilton cycles and perfect matchings in the KPKVB model

Research output: Contribution to journalArticlepeer-review

Standard

Hamilton cycles and perfect matchings in the KPKVB model. / Fountoulakis, Nikolaos; Muller, Tobias; Mitsche, Dieter; Schepers, Markus.

In: Stochastic Processes and their Applications, 06.09.2020.

Research output: Contribution to journalArticlepeer-review

Harvard

APA

Vancouver

Author

Bibtex

@article{08c6760f8a214c508ea3fb6a42a864aa,
title = "Hamilton cycles and perfect matchings in the KPKVB model",
abstract = "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 α, ν > 0, which we think of as constant. Roughly speaking α controls the power law exponent of the degree sequence and ν the average degree. Here we show that for every α < 1/2 and ν = ν(α) sufficiently small, the model does not contain a perfect matching with high probability, whereas for every α < 1/2 and ν = ν(α) sufficiently large, the model contains a Hamilton cycle with high probability.",
keywords = "hyperbolic random graphs, Hamilton cycles, perfect matchings, threshold",
author = "Nikolaos Fountoulakis and Tobias Muller and Dieter Mitsche and Markus Schepers",
year = "2020",
month = sep,
day = "6",
doi = "10.1016/j.spa.2020.09.012",
language = "English",
journal = "Stochastic Processes and their Applications",
issn = "0304-4149",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - Hamilton cycles and perfect matchings in the KPKVB model

AU - Fountoulakis, Nikolaos

AU - Muller, Tobias

AU - Mitsche, Dieter

AU - Schepers, Markus

PY - 2020/9/6

Y1 - 2020/9/6

N2 - 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 α, ν > 0, which we think of as constant. Roughly speaking α controls the power law exponent of the degree sequence and ν the average degree. Here we show that for every α < 1/2 and ν = ν(α) sufficiently small, the model does not contain a perfect matching with high probability, whereas for every α < 1/2 and ν = ν(α) sufficiently large, the model contains a Hamilton cycle with high probability.

AB - 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 α, ν > 0, which we think of as constant. Roughly speaking α controls the power law exponent of the degree sequence and ν the average degree. Here we show that for every α < 1/2 and ν = ν(α) sufficiently small, the model does not contain a perfect matching with high probability, whereas for every α < 1/2 and ν = ν(α) sufficiently large, the model contains a Hamilton cycle with high probability.

KW - hyperbolic random graphs

KW - Hamilton cycles

KW - perfect matchings

KW - threshold

U2 - 10.1016/j.spa.2020.09.012

DO - 10.1016/j.spa.2020.09.012

M3 - Article

JO - Stochastic Processes and their Applications

JF - Stochastic Processes and their Applications

SN - 0304-4149

ER -