Structural properties of Toeplitz graphs

Abstract

In this paper, we study structural properties of Toeplitz graphs. We characterize $K_q$-free Toeplitz graphs for an integer $q\ge 3$ and give equivalent conditions for a Toeplitz graph $G_n⟨t_1,t_2,\dots ,t_k⟩$ with $t_1<\cdots <t_k$ and $n\ge t_{k-1}+t_k$ being chordal and equivalent conditions for a Toeplitz graph $G_n⟨t_1,t_2⟩$ being perfect. Then we compute the edge clique cover number and the vertex clique cover number of a chordal Toeplitz graph. Finally, we characterize the degree sequence $(d_1,d_2,\dots ,d_n)$ of a Toeplitz graph with $n$ vertices and show that a Toeplitz graph is a regular graph if and only if it is a circulant graph.

20 pages, 2 figures