Three infinite families of Hamilton-connected convex polytopes and their detour index

A path in a graph encompassing its whole vertex set is called Hamiltonian. Such a path with sharing the same initial and terminal vertices is called a Hamiltonian cycle. A graph comprising a Hamiltonian path (resp. cycle) is said to be traceable (resp. Hamiltonian). Graphs possessing Hamiltonian paths between every pair of their vertices are said to be Hamilton-connected. The computational complexity of evaluating a graph to be Hamilton-connected is NP-complete. A detour is the longest path in a graph. The detour index is the sum of the length of detours between every unordered pair of vertices. Computing the detour index of a graph is an NP-complete problem as well. A finite subset $P\subset {\mathbb{R}}^{\epsilon }$ is called a convex polytope if $P$ is a convex hull. In this paper, we devised two distinct methods to prove a graph to be Hamilton-connected and employed these methods to construct some infinite families of Hamilton-connected convex polytopes. The convex polytope $B_{\epsilon }$ has been shown to be non-Hamilton-connected in the literature. We showed that the existing proof for $B_{\epsilon }$ is false and showed that this family is, in fact, Hamilton-connected. The paper is concluded with study implications followed by some future directions.