Perfect matchings and Hamiltonian cycles in the preferential attachment model. Issue 2 (6th April 2018)

• Record Type: Journal Article
• Authors: Frieze, Alan; Pérez‐Giménez, Xavier; Prałat, Paweł; Reiniger, Benjamin
• Is Part Of: Random structures & algorithms. Volume 54:Issue 2(2019)
• Page Start: 258
• Page End: 288
• Publication Date: 2018-04-06
• Subjects: Hamiltonian cycles -- perfect matchings -- preferential attachment model; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20778
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In this paper, we study the existence of perfect matchings and Hamiltonian cycles in the preferential attachment model. In this model, vertices are added to the graph one by one, and each time a new vertex is created it establishes a connection with m random vertices selected with probabilities proportional to their current degrees. (Constant m is the only parameter of the model.) We prove that if m ≥ 1253, then asymptotically almost surely there exists a perfect matching. Moreover, we show that there exists a Hamiltonian cycle asymptotically almost surely, provided that m ≥ 29 500 . One difficulty in the analysis comes from the fact that vertices establish connections only with vertices that are "older" (ie, are created earlier in the process). However, the main obstacle arises from the fact that edges in the preferential attachment model are not generated independently. In view of that, we also consider a simpler setting—sometimes called uniform attachment—in which vertices are added one by one and each vertex connects to m older vertices selected uniformly at random and independently of all other choices. We first investigate the existence of perfect matchings and Hamiltonian cycles in the uniform attachment model, and then extend the argument to the preferential attachment version.