×

zbMATH — the first resource for mathematics

Perfect matchings and Hamiltonian cycles in the preferential attachment model. (English) Zbl 1417.05188
This paper deals with B. Bollobás and O. Riordan’s [Combinatorica 24, No. 1, 5–34 (2004; Zbl 1047.05038)] generative preferential attachment model of random graphs where new nodes are added to the graph successively and every new node is connected to \(m\) existing nodes, more likely to those with higher degree than to those with lower degree. Here, the value of \(m\) is considered the only parameter of the model. The following two are the main results of the paper under review:
(1)
If \(m \geqslant 1\,253\), then asymptotically almost surely the random graph contains a perfect matching.
(2)
If \(m \geqslant 29\,500\), then asymptotically almost surely the random graph contains a Hamiltonian cycle.
The main difficulty in obtaining these results is due to the lack of independence in generating new edges in the preferential attachment model. To overcome this difficulty, the authors first consider the uniform attachment model where new nodes are added to the graph successively but are uniformly likely to be connected to \(m\) existing nodes chosen independently. The authors first establish the almost sure existence of a perfect matching and a Hamiltonian cycle in the uniform attachment model, and then adjust the construction to the preferential attachment model.

MSC:
05C80 Random graphs (graph-theoretic aspects)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C45 Eulerian and Hamiltonian graphs
PDF BibTeX XML Cite
Full Text: DOI