Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs

DOI10.1006/JCTB.2000.1991zbMATH Open1030.05107OpenAlexW2053929306MaRDI QIDQ1850508FDOQ1850508

Authors: Jeong Han Kim, Nicholas Wormald 

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/cce5f54af5c5d63d5445a6de855e6518b3120bf3

Recommendations

• Hamiltonian decompositions of random bipartite regular graphs.
• scientific article; zbMATH DE number 3950585
• Proof of the 1-factorization and Hamilton decomposition conjectures
• Almost all regular graphs are hamiltonian
• Proof of the 1-factorization and Hamilton Decomposition Conjectures

zbMATH Keywords

perfect matchingsHamilton cycleedge-decompositionasymptotic probability

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Almost all regular graphs are hamiltonian
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• Generating Random Regular Graphs Quickly
• Almost all cubic graphs are Hamiltonian
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generating and Counting Hamilton Cycles in Random Regular Graphs

Cited In (22)

• Title not available (Why is that?)
• Packing tight Hamilton cycles in 3-uniform hypergraphs
• Hamilton decompositions of regular expanders: applications
• Approximate Hamilton decompositions of random graphs
• Hamiltonian decompositions of random bipartite regular graphs.
• On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
• Almost all regular graphs are hamiltonian
• Cleaning random \(d\)-regular graphs with brooms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Resilient degree sequences with respect to Hamilton cycles and matchings in random graphs
• Edge-disjoint Hamilton cycles in random graphs
• Finding a second Hamiltonian decomposition of a 4-regular multigraph by integer linear programming
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• The number of Hamiltonian decompositions of regular graphs
• Cleaning Random d-Regular Graphs with Brushes Using a Degree-Greedy Algorithm
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Backtracking Algorithms for Constructing the Hamiltonian Decomposition of a 4-regular Multigraph
• Even cycle decompositions of 4-regular graphs and line graphs
• Permutations resilient to deletions
• The maximum fuzzy weighted matching models and hybrid genetic algorithm
• On packing Hamilton cycles in \(\varepsilon\)-regular graphs

This page was built for publication: Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850508)