Improved upper bounds on even-cycle creating Hamilton paths

2023/04/04 by John H. Byrne, Byrne, John, Michael Tait +1 · 1 citation
Mathematics · #Advanced Combinatorial Mathematics #Analytic Number Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2304.02164

openalex publication_date 2023/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01

Abstract

We study the function H_n(C_2k), the maximum number of Hamilton paths such that the union of any pair of them contains C_2k as a subgraph. We give upper bounds on this quantity for k≥ 3, improving results of Harcos and Soltész, and we show that if a conjecture of Ustimenko is true then one additionally obtains improved upper bounds for all k≥ 6. We also give bounds on H_n(K_2,3) and H_n(K_2,4). In order to prove our results, we extend a theorem of Krivelevich which counts Hamilton cycles in (n, d, λ)-graphs to bipartite or irregular graphs, and then apply these results to generalized polygons and the constructions of Lubotzky-Phillips-Sarnak and Füredi.

Cited by

• New constructions and bounds for nonabelian Sidon sets with applications to Turán-type problems

Related

• Families of graph-different Hamilton paths
• Counting and packing Hamilton cycles in dense graphs and oriented graphs
• Families of locally separated Hamilton paths
• Optimal packings of Hamilton cycles in graphs of high minimum degree
• Upper Bounds for the Number of Hamiltonian Cycles