The Property of Hamiltonian Connectedness in Toeplitz Graphs. (12th March 2020) - Shabbir, Ayesha; Nadeem, Muhammad Faisal; Zamfirescu, Tudor
Abstract : 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 p, q is Hamiltonian-connected, while some particular cases of T n p, 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 T n 1, q, r is Hamiltonian-connected for all 1 < q < r < n and n ≥ 5 r − 2 .