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 (4)

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

This page was built for publication: Perfect matchings and Hamiltonian cycles in the preferential attachment model