Inclusion of Trees in Their Iterated Line Graphs

Abstract

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}$.