The property of Hamiltonian connectedness in Toeplitz graphs (Q2173741)

Summary: A spanning path in a graph \(G\) is called a Hamiltonian path. To determine which graphs possess such paths is an NP-complete problem. A graph \(G\) is called Hamiltonian-connected if any two vertices of \(G\) are connected by a Hamiltonian path. We consider here the family of Toeplitz graphs. About them, it is known only for \(n=3\) that \(T_n\left\langle p, q\right\rangle\) is Hamiltonian-connected, while some particular cases of \(T_n\left\langle p, q, r\right\rangle\) for \(p=1\) and \(q=2,3,4\) have also been investigated regarding Hamiltonian connectedness. Here, we prove that the nonbipartite Toeplitz graph \(T_n\left\langle 1, q, r\right\rangle\) is Hamiltonian-connected for all \(1<q<r<n\) and \(n\geq5r-2\).