Edge Degree Conditions for 2-Iterated Line Graphs to Be Traceable

The line graph (Formula presented.) of G has (Formula presented.) as its vertex set, and two vertices are adjacent in (Formula presented.) if and only if the corresponding edges share a common end vertex in G. Let (Formula presented.). We show that, if (Formula presented.) and n is sufficiently large, then either (Formula presented.) is traceable or the Veldman’s reduction (Formula presented.) is one of well-defined classes of exceptional graphs. Furthermore, if (Formula presented.) and n is sufficiently large, then (Formula presented.) is traceable. The bound (Formula presented.) is sharp. As a byproduct, we characterize the structure of a connected graph with a non-traceable 2-iterated line graph.