Hamiltonian properties in iterated line graphs

For integer n, the n-iterated line graph L^n(G) of an undirected graph G is defined to be L(L^{n-1}(G)), where L^1(G)=L(G). Chartrand considered the n-iterated line graphs and introduced the concept of hamiltonian index of a graph. The hamiltonian index, denoted by h(G), is the minimum number n such that L^n(G) is hamiltonian. He showed that for any graph G other than a path, the hamiltonian index of G exists. It is well known a lot of results dealing with exact value of h(G) for some special classes of graphs or upper and lower bounds on h(G) for wider classes of graphs.

In this talk we give some these basic results and introduce hamiltonian path index. Maybe surprisingly there are not too much known results for the existence of hamiltonian paths in iterated line graphs. Hamiltonian path index, denoted by h_p(G), is the minimum number n such that L^n(G) is traceable, it means that L^n(G) contains a hamiltonian path. Clearly h_p(G)\leq h(G) for all graphs except paths and h_p(P)=0 for every path P. Hence hamiltonian path index of G exists for any graph G. We set the exact value of hamiltonian path index for trees and graphs with hamiltonian 2-connected blocks. At the end we mention our next aim and some open problems in this area.