Almost all regular graphs are hamiltonian

DOI10.1002/RSA.3240050209zbMATH Open0795.05088DBLPjournals/rsa/RobinsonW94OpenAlexW2136219960WikidataQ55954091 ScholiaQ55954091MaRDI QIDQ4286301FDOQ4286301

Authors: R. W. Robinson, Nicholas Wormald 

Publication date: 11 September 1994

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

Full work available at URL: https://doi.org/10.1002/rsa.3240050209

Recommendations

• Hamiltonian cycles in random regular graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Random Regular Graphs of Non-Constant Degree: Connectivity and Hamiltonicity
• Proof of the 1-factorization and Hamilton Decomposition Conjectures
• Hamilton cycles containing randomly selected edges in random regular graphs

zbMATH Keywords

perfect matchingsedge decomposition\(r\)-regular graphshamilton cycle\(r\)-edge-colorable

Mathematics Subject Classification ID

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

Cites Work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• The number of matchings in random regular graphs and bipartite graphs
• The asymptotic number of non-negative integer matrices with given row and column sums
• The asymptotic distribution of short cycles in random regular graphs
• Hamiltonian cycles in random regular graphs
• Finding Hamilton cycles in sparse random graphs

Cited In (82)

• A threshold result for loose Hamiltonicity in random regular uniform hypergraphs
• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Statistical limits of spiked tensor models
• On cycle lengths in claw-free graphs with complete closure
• Deterministic counting of graph colourings using sequences of subgraphs
• Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results
• Spanning trees in random regular uniform hypergraphs
• Recent advances on the Hamiltonian problem: survey III
• Edge-colorings of 4-regular graphs with the minimum number of palettes
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• On groups and simplicial complexes
• 3-star factors in random \(d\)-regular graphs
• Phase transitions in discrete structures
• Dynamics of random graphs with bounded degrees
• The number of Euler tours of random directed graphs
• On the number of circuits in random graphs
• A conjecture on the prevalence of cubic bridge graphs
• Planting colourings silently
• Hamiltonian decompositions of random bipartite regular graphs.
• Satisfiability threshold for random regular \textsc{nae-sat}
• Perfect Matchings in Random r-regular, s-uniform Hypergraphs
• Hamilton cycles in 3-out
• Nowhere-zero flows in random graphs
• Orthogonal double covers of general graphs.
• Proper connection number of random graphs
• Hamiltonian cycle curves in the space of discounted occupational measures
• An explicit construction of graphs of bounded degree that are far from being Hamiltonian
• On the number of perfect matchings in random lifts
• On the chromatic number of random regular graphs
• Random Regular Graphs: Asymptotic Distributions and Contiguity
• On the chromatic number of random \(d\)-regular graphs
• On the number of solutions in random hypergraph 2-colouring
• The number of perfect matchings, and the nesting properties, of random regular graphs
• Rainbow Hamilton cycles in random graphs
• Hamilton cycles containing randomly selected edges in random regular graphs
• An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three
• A transition of limiting distributions of large matchings in random graphs
• Small maximal matchings of random cubic graphs
• Constructions of Hamiltonian graphs with bounded degree and diameter \(O(\log n)\)
• Loose Hamilton Cycles in Regular Hypergraphs
• Distribution of the number of spanning regular subgraphs in random graphs
• Conflict-free connection number of random graphs
• Harnessing the Bethe free energy
• Hamiltonian paths in Cayley graphs
• Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs
• Acyclic edge colorings of graphs
• Increasing Hamiltonian paths in random edge orderings
• Reconstruction and estimation in the planted partition model
• The number of Hamiltonian decompositions of regular graphs
• Local resilience and hamiltonicity maker-breaker games in random regular graphs
• Locally quasiconvex small-cancellation groups
• On the Hamiltonicity gap and doubly stochastic matrices
• Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity
• Hamiltonicity of graphs perturbed by a random regular graph
• The matching process and independent process in random regular graphs and hypergraphs
• Cycle lengths in sparse random graphs
• On the Hamiltonicity of the \(k\)-regular graph game
• Counting cusped hyperbolic 3-manifolds that bound geometrically
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Hamiltonian cycles in random regular graphs
• Sandwiching random graphs: universality between random graph models
• Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes
• Random regular graphs of high degree
• Edge correlations in Random regular hypergraphs and applications to subgraph testing
• Community detection in sparse random networks
• On Hamilton cycles in Erdős-Rényi subgraphs of large graphs
• Getting a directed Hamilton cycle two times faster
• Dirac's theorem for random regular graphs
• Hamiltonicity of randomly perturbed graphs
• Critical window of the symmetric perceptron
• On the path partition number of 6‐regular graphs
• Methods for determining cycles of a specific length in undirected graphs with edge weights
• On \(r\)-regular subgraphs with Hamiltonian cycles in graphs with many edges
• Resilience with respect to Hamiltonicity in random graphs
• Hamilton cycles in pseudorandom graphs
• Decomposition of \(4k\)-regular graphs into \(k\, 4\)-regular \(K_5\)-free and \((K_5\text{-}e)\)-free subgraphs
• On the number of solutions in random graph \(k\)-colouring
• The asymptotic distribution of the number of 3-star factors in random \(d\)-regular graphs
• One-step replica symmetry breaking of random regular NAE-SAT. II
• The hardness of recognising poorly matchable graphs and the hunting of the \(d\)-snark
• Hamilton cycles in the union of random permutations
• On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three

This page was built for publication: Almost all regular graphs are hamiltonian

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