论文标题
在toeplitz图上是线图
On Toeplitz graphs being line graphs
论文作者
论文摘要
a toeplitz图$ t_n \ langle t_1，t_2，\ ldots，t_k \ rangle $是一个简单的图形，带有顶点set $ [n] $，因此两个顶点$ v $ and $ w $在且仅当$ | v-w | = t_i $对于某些$ i \ in [k] $。 在本文中，我们研究了线Toeplitz图，这些图是恰好是线图的Toeplitz图。 我们首先表明，对于足够大的$ n $，无爪toeplitz的订单$ n $的家族是$ t_n \ langle t，2t，\ ldots，\ ldots，kt \ rangle $，用于某些非阴性整数$ t $和$ k $。 有趣的是，这个家庭由toeplitz图组成，每个图形与$ k $ -tree是同构的。 然后，我们完全表征$ t_n \ langle t，2t，\ ldots，kt \ rangle $，用于任何正面整数$ n $，即线图。 此外，我们提供了一条toeplitz图的全面描述$ t_n \ langle t_1，t_2 \ rangle $和$ t_n \ langle t_1，t_2，t_3 \ rangle $。 通常，Line Toeplitz图似乎非常具有挑战性。即使对于$ t_n \ langle t_1，t_2，t_3 \ rangle $，也不容易这样做。 还值得一提的是，有一个线条toeplitz图，该图的形式不在$ t_n \ langle t，2t，3t \ rangle $中。
A Toeplitz graph $T_n \langle t_1,t_2,\ldots,t_k\rangle$ 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 \langle t,2t,\ldots,kt\rangle$ 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 \langle t,2t,\ldots,kt\rangle$ for any positive integer $n$ that is a line graph. Furthermore, we provide a comprehensive description of a line Toeplitz graph $T_n \langle t_1,t_2\rangle$ and $T_n \langle t_1,t_2,t_3\rangle$. In general, line Toeplitz graph seems very challenging to characterize completely. Even for $T_n \langle t_1,t_2,t_3\rangle$, 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 \langle t,2t,3t\rangle$.
