Perfect matchings and Hamiltonian cycles in the preferential attachment model.

*(English)*Zbl 1417.05188This 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.

Reviewer: Serge Lawrencenko (Moskva)

##### 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 |