An extremal problem for cycles in hamiltonian graphs (Q1900521)

For integers \(p\) and \(r\) with \(3 \leq r \leq p - 1\), let \(f(p,r)\) be the maximum number of edges in a hamiltonian graph of order \(p\) with no cycle of length \(r\). As a consequence of known facts it is remarked that \(f(p,3) = (p - 1)^2/4 + 1\). The main result states that \(f(p,5) = (p - 3)^2/4 + 5\) for all \(p \geq 7\), except \(p = 9\). In this last case there is a unique extremal graph, and \(f(9,5) = 15\). Lower bounds for \(f(p,r)\) are also established in several cases, with \(p\) and \(r\) odd. Some conjectures are proposed for the exact values, together with an explicit description of the candidates to be the corresponding extremal graphs.