The hamiltonian index of a graph (Q5956112)

The hamiltonian index \(\text{ham}(G)\) of a graph \(G\) is defined as the least \(n\) such that the \(n\)th iterated line graph \(L^n(G)=L(L^{n-1}(G))\) of \(G\) is hamiltonian. Improving results due to \textit{P. A. Catlin} et al. [J. Graph Theory 14, No. 3, 347-364 (1990; Zbl 0721.05044)] and \textit{M. Lovrečič Saražin} [Discrete Math. 134, No. 1-3, 85-91 (1994; Zbl 0815.05044)] the author proves that \(\text{ham}(G)\) of a connected graph \(G\) different from a path is strictly less than the diameter of \(G\). The proof relies on an extension of Harary and Nash-Williams' well-known characterization of hamiltonian line graphs that is due to the author and Z. Liu. Furthermore, the author proves that if \(G\) and its complement \(\overline{G}\) are connected simple graphs of order at least \(61\) different from a path, then \(\min\{ \text{ham}(G), \text{ham}(\overline{G})\}\leq 1\) and if \(\min\{ \text{ham}(G), \text{ham}(\overline{G})\}=1\), then \(\max\{ \text{ham}(G),\text{ham}(\overline{G})\}\leq \frac{n-1}{2}\). The proof relies on a result due to \textit{H.-J. Lai} [J. Graph Theory 17, No. 2, 263-273 (1993; Zbl 0781.05033)]. From this the author deduces some Nordhaus-Gaddum type relations.