On hamiltonian Toeplitz graphs (Q1348117)

Let \(n,m,a_1,\dots,a_m\in \mathbb{N}\), \(0<a_1<\cdots <a_m<n\) and \(V:=\{0,\dots,n-1\}\). Define \(E:=\{[i,j]\in V^2:|j-i|=a_k\) for some \(k\in\{1,\dots,m\}\}.\) Then the graph \((V,E)\) with set of vertices \(V\) and set of edges \(E\) is called an undirected Toeplitz graph with stripes \(a_1,\dots,a_m\). The author considers connectivity properties and hamiltonian properties of Toeplitz graphs. A sufficient condition for a Toeplitz graph to be connected is described and a complete characterization of connected Toeplitz graphs with two stripes is given. An infinite family of hamiltonian and of nonhamiltonian Toeplitz graphs with two stripes are described. Sufficient conditions for Toeplitz graphs with many entries to be hamiltonian are derived as well. Note that the circulant graphs are special Toeplitz graphs.