kk-ordered hamiltonicity of iterated line graphs

A graph GG of order nn is kk-ordered hamiltonian, 2≤k≤n2≤k≤n, if for every sequence v1,v2,…,vkv1,v2,…,vk of kk distinct vertices of GG, there exists a hamiltonian cycle that encounters v1,v2,…,vkv1,v2,…,vk in this order. In this paper, we generalize two well-known theorems of Chartrand on hamiltonicity of iterated line graphs to kk-ordered hamiltonicity. We prove that if Ln(G)Ln(G) is kk-ordered hamiltonian and nn is sufficiently large, then Ln+1(G)Ln+1(G) is (k+1)(k+1)-ordered hamiltonian. Furthermore, for any connected graph GG, which is not a path, cycle, or the claw K1,3K1,3, there exists an integer N′N′ such that LN′+(k−3)(G)LN′+(k−3)(G) is kk-ordered hamiltonian for k≥3k≥3.