Large connected strongly regular graphs are Hamiltonian

2014/09/10 by László Pyber, Pyber, László · 2 citations
Mathematics · #Finite Group Theory Research #Graph theory and applications #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.1409.3041

Abstract

We prove that every connected strongly regular graph on sufficiently many vertices is Hamiltonian. We prove this by showing that, apart from three families, connected strongly regular graphs are (highly) pseudo-random. Our results suggest a number of new questions and conjectures.

Cited by

• On Weisfeiler-Leman Invariance: Subgraph Counts and Related Graph Properties
• An improved bound for strongly regular graphs with smallest eigenvalue -m

Related

• Hamilton cycles in regular graphs perturbed by a random 2-factor
• Dirac's theorem for random regular graphs
• Solution to a problem of Bollob 'as and H "aggkvist on Hamilton cycles\n in regular graphs
• Hamiltonicity of Sparse Pseudorandom Graphs
• 10-tough chordal graphs are Hamiltonian