On the maximum number of cycles in a Hamiltonian graph

AbstractLet M(k) denote the maximum number of cycles in a Hamiltonian graph of order n and size n+k. We prove that M(k)⩾2k+(5/2)k2-(21/2)k+14 and M(k)⩽2k+1-1-kk-2log2(k)+2-14log2(k) for k⩾4. Furthermore, we determine M(k) and the structure of the extremal graphs for 5⩽k⩽10 exactly. Our results give partial answers to a problem raised by Shi [The number of cycles in a hamilton graph, Discrete Math. 133 (1994) 249–257]