Hamilton cycles and perfect matchings in the KPKVB model

Nikolaos Fountoulakis, Dieter Mitsche, Tobias Müller and Markus Schepers

Stochastic Processes and their Applications, 2021, vol. 131, issue C, 340-358

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.

Keywords: Hamilton cycle; Perfect matching; Hyperbolic random graph; Poisson process; Randomized algorithm; Tiling (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0304414920303720
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:spapps:v:131:y:2021:i:c:p:340-358

Ordering information: This journal article can be ordered from
http://http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.spa.2020.09.012

Access Statistics for this article

Stochastic Processes and their Applications is currently edited by T. Mikosch

More articles in Stochastic Processes and their Applications from Elsevier
Bibliographic data for series maintained by Catherine Liu ().