The Property of Hamiltonian Connectedness in Toeplitz Graphs

Abstract EN

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 Tnp,q is Hamiltonian-connected, while some particular cases of Tnp,q,r for p=1 and q=2,3,4 have also been investigated regarding Hamiltonian connectedness.

Here, we prove that the nonbipartite Toeplitz graph Tn1,q,r is Hamiltonian-connected for all 1