Hamiltonian iterated line graphs
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)].
- On distance local connectivity and the Hamiltonian index
- Hamilton-connected indices of graphs
- Closure, stability and iterated line graphs with a 2-factor
- On the hamiltonian index of a graph
- A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
- The Hamiltonian index of a graph and its branch-bonds
- On Hamiltonicity of 2-connected claw-free graphs
- Degree sum conditions for Hamiltonian index
- On the dominating (induced) cycles of iterated line graphs
- Hamiltonian index of directed multigraph
- Forbidden subgraphs on Hamiltonian index
- Even factors with a bounded number of components in iterated line graphs
- Hamiltonian connected hourglass free line graphs
- On the 2-factor index of a graph
- Local search algorithms for finding the Hamiltonian completion number of line graphs
- Linkability in iterated line graphs
- On computing the Hamiltonian index of graphs
- Branch-bonds, two-factors in iterated line graphs and circuits in weighted graphs
- Forbidden subgraphs and the Hamiltonian index of a 2-connected graph.
- Induced hourglass and the equivalence between Hamiltonicity and supereulerianity in claw-free graphs
- Spanning connectivity of the power of a graph and Hamilton-connected index of a graph
- Catlin's reduced graphs with small orders
- Edge degree conditions for Hamiltonian 2-iterated line graphs
- On Computing the Hamiltonian Index of Graphs
- Connectivity of iterated line graphs
- Hamiltonian index is NP-complete
- On traceable iterated line graph and Hamiltonian path index
- The Wiener index in iterated line graphs
- Minimum number of components of 2-factors in iterated line graphs
- The Chvàtal-Erdős condition for supereulerian graphs and the Hamiltonian index
- The hamiltonian index of a 2-connected graph
- The existence of even factors in iterated line graphs
- The Hamiltonian index of graphs
This page was built for publication: Hamiltonian iterated line graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849948)
