Perfect matchings and Hamilton cycles in uniform attachment graphs

2019/08/10 by Acan, Huseyin
#05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1908.03659

Abstract

We study Hamilton cycles and perfect matchings in a uniform attachment graph. In this random graph, vertices are added sequentially, and when a vertex t is created, it makes k independent and uniform choices from \1,…,t-1\ and attaches itself to these vertices. Improving the results of Frieze, Pérez-Giménez, Prałat and Reiniger (2019), we show that, with probability approaching 1 as n tends to infinity, a uniform attachment graph on n vertices has a perfect matching for k ≥ 5 and a Hamilton cycle for k≥ 13. One of the ingredients in our proofs is the identification of a subset of vertices that is least likely to expand, which provides us with better expansion rates than the existing ones.

Related

• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Perfect matchings and loose Hamilton cycles in the semirandom hypergraph model
• On Kotzig's conjecture in random graphs
• Rainbow perfect matchings and Hamilton cycles in the random geometric\n graph
• Constructing Hamilton cycles and perfect matchings efficiently