Inclusion of Trees in Their Iterated Line Graphs

Bauer and Tindell defined the graph invariant \(\wedge(G)\), for graphs \(G\) other than paths and the star \(K_{1,3}\), to be the least \(n\) for which \(G\) embeds in the \(n\)th iterated line graph of \(G\). They also proposed the problem of determining \(\wedge(T)\) for all trees \(T\). In this note, we completely solve this problem by showing that \(\wedge(T) = 3\) for any proper homeomorph \(T\) of \(K_{1,3}\) and that \(\wedge(T) = 2\) for all trees \(T\) which are neither paths nor homeomorphs of \(K_{1,3}\).