The Property of Hamiltonian Connectedness in Toeplitz Graphs. (12th March 2020)

• Record Type: Journal Article
• Authors: Shabbir, Ayesha; Nadeem, Muhammad Faisal; Zamfirescu, Tudor
• Other Names: Volchenkov Dimitri Academic Editor.
• Is Part Of: Complexity. Volume 2020(2020)
• Publication Date: 2020-03-12
• Subjects: Chaotic behavior in systems -- Periodicals; Complexity (Philosophy) -- Periodicals; 003
• DOI: 10.1155/2020/5608720
• Languages: English
• ISSNs: 1076-2787

Abstract

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 .