Improved upper bounds on even-cycle creating Hamilton paths

arXiv2304.02164MaRDI QIDQ6432115FDOQ6432115

Authors: John H. Byrne, Michael Tait 

Publication date: 4 April 2023

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 $kin3,4,5$, improving results of Harcos and Solt'esz, and we show that if a conjecture of Ustimenko is true then one additionally obtains improved upper bounds for all $kgeq6$. In order to prove our results, we extend a theorem of Krivelevich which counts Hamilton cycles in $(n,d,lambda)$-graphs to graphs which are not regular, and then apply this result to graphs constructed from polarity graphs of generalized polygons.

This page was built for publication: Improved upper bounds on even-cycle creating Hamilton paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6432115)