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