Almost all regular graphs are hamiltonian

DOI10.1002/RSA.3240050209zbMath0795.05088DBLPjournals/rsa/RobinsonW94OpenAlexW2136219960WikidataQ55954091 ScholiaQ55954091MaRDI QIDQ4286301

Nicholas C. Wormald, Robert W. Robinson

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

zbMATH Keywords

perfect matchings edge decomposition \(r\)-regular graphs hamilton cycle \(r\)-edge-colorable

Mathematics Subject Classification ID

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

Related Items (76)

Spanning trees in random regular uniform hypergraphs ⋮ Phase transitions in discrete structures ⋮ Sandwiching random graphs: universality between random graph models ⋮ Edge-colorings of 4-regular graphs with the minimum number of palettes ⋮ On the number of circuits in random graphs ⋮ Getting a Directed Hamilton Cycle Two Times Faster ⋮ Some remarks on rainbow connectivity ⋮ 3-star factors in random \(d\)-regular graphs ⋮ An almost linear time algorithm for finding Hamilton cycles in sparse random graphs with minimum degree at least three ⋮ Embedding the Erdős-Rényi hypergraph into the random regular hypergraph and Hamiltonicity ⋮ On a greedy 2-matching algorithm and Hamilton cycles in random graphs with minimum degree at least three ⋮ On the number of solutions in random hypergraph 2-colouring ⋮ Statistical limits of spiked tensor models ⋮ The number of Euler tours of random directed graphs ⋮ The number of Hamiltonian decompositions of regular graphs ⋮ Cycle lengths in sparse random graphs ⋮ On the path partition number of 6‐regular graphs ⋮ Harnessing the Bethe free energy ⋮ Hamiltonicity of graphs perturbed by a random regular graph ⋮ The number of perfect matchings, and the nesting properties, of random regular graphs ⋮ Community detection in sparse random networks ⋮ Conflict-free connection number of random graphs ⋮ A transition of limiting distributions of large matchings in random graphs ⋮ On the chromatic number of random regular graphs ⋮ One-step replica symmetry breaking of random regular NAE-SAT. II ⋮ Proper connection number of random graphs ⋮ Critical window of the symmetric perceptron ⋮ Methods for determining cycles of a specific length in undirected graphs with edge weights ⋮ Loose Hamilton Cycles in Regular Hypergraphs ⋮ Planting Colourings Silently ⋮ Random Regular Graphs: Asymptotic Distributions and Contiguity ⋮ On Hamilton cycles in Erdős‐Rényi subgraphs of large graphs ⋮ Recent advances on the Hamiltonian problem: survey III ⋮ Hamiltonian decompositions of random bipartite regular graphs. ⋮ Perfect Matchings in Random r-regular, s-uniform Hypergraphs ⋮ Orthogonal double covers of general graphs. ⋮ Perfect matchings and Hamiltonian cycles in the preferential attachment model ⋮ Dynamics of random graphs with bounded degrees ⋮ Reconstruction and estimation in the planted partition model ⋮ A threshold result for loose Hamiltonicity in random regular uniform hypergraphs ⋮ On groups and simplicial complexes ⋮ Acyclic edge colorings of graphs ⋮ Random regular graphs of high degree ⋮ On the Number of Perfect Matchings in Random Lifts ⋮ Hamilton cycles containing randomly selected edges in random regular graphs ⋮ On the Hamiltonicity of the \(k\)-regular graph game ⋮ On cycle lengths in claw-free graphs with complete closure ⋮ Rainbow hamilton cycles in random graphs ⋮ Hamilton cycles in the union of random permutations ⋮ Locally quasiconvex small-cancellation groups ⋮ On the Hamiltonicity Gap and doubly stochastic matrices ⋮ Hamilton cycles in 3-out ⋮ Satisfiability threshold for random regular \textsc{nae-sat} ⋮ Counting cusped hyperbolic 3-manifolds that bound geometrically ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ Increasing Hamiltonian paths in random edge orderings ⋮ Local Resilience and Hamiltonicity Maker–Breaker Games in Random Regular Graphs ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ THE ASYMPTOTIC DISTRIBUTION OF THE NUMBER OF 3-STAR FACTORS IN RANDOM d-REGULAR GRAPHS ⋮ Geometric interpretation of Hamiltonian cycles problem via singularly perturbed Markov decision processes ⋮ Small maximal matchings of random cubic graphs ⋮ Edge Correlations in Random Regular Hypergraphs and Applications to Subgraph Testing ⋮ Constructions of Hamiltonian graphs with bounded degree and diameter \(O(\log n)\) ⋮ Deterministic counting of graph colourings using sequences of subgraphs ⋮ Dirac’s theorem for random regular graphs ⋮ On the chromatic number of random \(d\)-regular graphs ⋮ Hamiltonian paths in Cayley graphs ⋮ Ferromagnetic Potts Model: Refined #BIS-hardness and Related Results ⋮ Distribution of the number of spanning regular subgraphs in random graphs ⋮ Hamiltonian cycle curves in the space of discounted occupational measures ⋮ Random matchings which induce Hamilton cycles and Hamiltonian decompositions of random regular graphs ⋮ Nowhere-zero flows in random graphs ⋮ Decomposition of 4k-regular graphs into k 4-regular K5-free and (K5 − e)-free subgraphs ⋮ Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio ⋮ An explicit construction of graphs of bounded degree that are far from being Hamiltonian ⋮ The matching process and independent process in random regular graphs and hypergraphs

Cites Work

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