Structural properties of Toeplitz graphs

Abstract

In this paper, we study structural properties of Toeplitz graphs. We characterize Kqfree Toeplitz graphs for an integer q > 3 and give equivalent conditions for a Toeplitz graph Gn(t1, t2, ... , tk) with t1 < center dot center dot center dot < tk and n > tk-1 + tk being chordal and equivalent conditions for a Toeplitz graph Gn(t1, t2) 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 (d1, d2, ..., dn) 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. (c) 2022 Elsevier B.V. All rights reserved.