2023/05/15 by Michael Krivelevich, Krivelevich, Michael
Computer Science · Mathematics · #05C45 #05C80 #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2305.08442
openalex publication_date 2023/05/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A crown with k spikes is an edge-disjoint union of a cycle C and a matching M of size k such that each edge of M has exactly one vertex in common with C. We prove that if G is an (n,d,λ)-graph with λ/d≤ 0.001 and d is large enough, then G contains a crown on n vertices with \lfloor n/2\rfloor spikes. As a consequence, such G contains a Hamilton cycle in its square G2.