Hamiltonian properties of Toeplitz graphs (Q1126180)

A Toeplitz graph is an undirected graph that has an adjacency matrix in which all of the entries are the same in any diagonal parallel to the main diagonal. The Toeplitz graph \(T_n(t_1,t_2,\dots,t_k)\) has adjacency matrix with \(k\) nonzero diagonals that contain the \(k\) rows \(0<t_1<t_2<\cdots<t_k\leq n\). Hamiltonian properties (Hamiltonicity, traceability) of these graphs are investigated. For example it is shown that the Toeplitz graph \(T_n(1,t_2,\dots,t_k)\) is Hamiltonian if and only if either \(n,t_2,\dots,t_k\) are not all of the same parity or they all are even and \(t_2\leq n/2\).