Hamiltonian iterated line graphs (Q1849948)

The Hamiltonian index \(h(G)\) of a connected multigraph \(G\) other than a path is defined as the minimum integer \(n\) such that \(L^n(G)\) is Hamiltonian, where \(L(G)=L^1(G)\) denotes the line graph of \(G\) and \(L^n(G)=L(L^n(G))\). A well-known theorem of \textit{F. Harary} and \textit{C. S. J. A. Nash-Williams} [Can. Math. Bull. 8, 701-709 (1965; Zbl 0136.44704)] says that \(h(G)=1\) iff \(G\) has a Eulerian subgraph \(S\) such that each edge of \(G\) is incident with a vertex of \(S\). In the paper under review, this classical result is extended to a characterization of multigraphs of Hamiltonian index \(n\geq 2\), given in terms of existence of certain Eulerian subgraphs. The main theorem is then used to obtain results that might be helpful when designing an algorithm for finding \(h(G)\). While the problem to determine \(h(G)\) is known to be NP-hard [\textit{A. A. Bertossi}, Inf. Process. Lett. 13, 157-159 (1981; Zbl 0495.68058)] in general, the authors conjecture that it can be solved in polynomial time provided \(h(G)\geq 2\). Another application of the main theorem is an upper bound on \(h(G)\), which implies previously published upper bounds on \(h(G)\) for multigraphs with minimum degree at least three [\textit{G. Chartrand} and \textit{C. E. Wall}, Studia Sci. Math. Hungar. 8(1973), 43-48 (1974; Zbl 0279.05121)] or graphs with maximum degree at least three [\textit{M. L. Saražin}, Discrete Math. 134, 85-91 (1994; Zbl 0815.05044)].