On Toeplitz graphs being line graphs

Abstract

A Toeplitz graph $T_n⟨t_1,t_2,\dots ,t_k⟩$ is a simple graph with the vertex set $[n]$ such that two vertices $v$ and $w$ are adjacent if and only if $|v-w|=t_i$ for some $i\in [k]$. In this paper, we investigate line Toeplitz graphs, which are Toeplitz graphs that happen to be line graphs. We first show that for a sufficiently large $n$, the family of claw-free Toeplitz graphs of order $n$ is $T_n⟨t,2t,\dots ,kt⟩$ for some nonnegative integers $t$ and $k$. Interestingly, this family consists of a union of Toeplitz graphs each of which is isomorphic to a $k$-tree the notion of which was introduced by Patil in 1986. Then we completely characterize $T_n⟨t,2t,\dots ,kt⟩$ for any positive integer $n$ that is a line graph. Furthermore, we provide a comprehensive description of a line Toeplitz graph $T_n⟨t_1,t_2⟩$ and $T_n⟨t_1,t_2,t_3⟩$. In general, line Toeplitz graph seems very challenging to characterize completely. Even for $T_n⟨t_1,t_2,t_3⟩$, it was not easy to do so. It is also worth mentioning that there is a line Toeplitz graph that is not in the form $T_n⟨t,2t,3t⟩$.

19 pages, 5 figure