Improved upper bounds on even-cycle creating Hamilton paths

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\ge 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\ge 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,\lambda )$-graphs to bipartite or irregular graphs, and then apply these results to generalized polygons and the constructions of Lubotzky-Phillips-Sarnak and Füredi.

improved results: we now improve previous bounds for all even cycles of length at least 6. Additionally we discuss the cases corresponding to K_{2,3} and K_{2,4}