Perfect matchings and Hamiltonian cycles in the preferential attachment model

DOI10.1002/rsa.20778zbMath1417.05188arXiv1610.07988OpenAlexW2963878853WikidataQ57991407 ScholiaQ57991407MaRDI QIDQ4633318

Benjamin Reiniger, Xavier Pérez-Giménez, Paweł Prałat, Alan M. Frieze

Publication date: 2 May 2019

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1610.07988

zbMATH Keywords

Hamiltonian cycledegree distributionperfect matchingpreferential attachment modeluniform attachment model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Eulerian and Hamiltonian graphs (05C45)

Related Items

The robot crawler graph process, Giant descendant trees, matchings, and independent sets in age-biased attachment graphs, On Bollobás‐Riordan random pairing model of preferential attachment graph, On the independence number and the chromatic number of generalized preferential attachment models

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Partitioning edge-coloured complete graphs into monochromatic cycles and paths
• The size Ramsey number of a directed path
• Hamilton cycles in random geometric graphs
• The robot cleans up
• Limit distribution for the existence of Hamiltonian cycles in a random graph
• Finding Hamilton cycles in sparse random graphs
• Hamiltonian circuits in random graphs
• Size-Ramsey numbers of cycles versus a path
• On the existence of Hamiltonian cycles in a class of random graphs
• The diameter of a scale-free random graph
• Sudden emergence of a giant \(k\)-core in a random graph
• The degree sequence of a scale-free random graph process
• Random regular graphs of high degree
• Random Graphs, Geometry and Asymptotic Structure
• Long cycles in subgraphs of (pseudo)random directed graphs
• Hamilton cycles in 3-out
• Emergence of Scaling in Random Networks
• Disjoint Hamilton cycles in the random geometric graph
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• The Robot Crawler Number of a Graph
• Almost all regular graphs are hamiltonian
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• On some Multicolor Ramsey Properties of Random Graphs
• An Alternative Proof of the Linearity of the Size-Ramsey Number of Paths
• Path Ramsey Number for Random Graphs
• Sharp Threshold for Hamiltonicity of Random Geometric Graphs
• On the existence of a factor of degree one of a connected random graph