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

1.   Introduction

In this paper, all graphs are assumed to be simple, finite, connected, and without loops. Any terms not explicitly defined can be found in Section 2.

Ore in 1963 ^[24] was the first graph-theorist who put forward the notion of Hamilton-connected structures, sparking significant research into the topics of Hamilton-connectedness and Hamiltonicity. Computational complexity of evaluating a graph to be Hamiltonian-connected or even Hamiltonian is categorized as NP-complete ^[11]. A study of cubic Hamiltonian graphs was conducted by Frucht ^[9] who delivered their canonical representations. In 1993, Wei ^[34] provided valency restrictions, which ensures a graph to possess pair-wise Hamiltonian paths. Wei ^[34] also demonstrated that any 3-connected graph meeting these conditions have to satisfy Hamilton-connectedness property. Yang et al. ^[38] presented a proof for Hamiltonicity of generalized torus graphs. Moreover, Hamiltonicity of triangular grid graphs was explored by Gordon et al. ^[12]. Additionally, Hamiltonian and super-Eulerian graphs were explored by Yang et al. ^[37] who pinpointed forbidden subgraphs in these structures. For more on applications of Hamiltonian paths and detours in communication systems and network design, we refer to ^[6,13,31,39].

The Hamilton-connectivity of block graph's square was proven by Chartrand et al. ^[7]. Hamiltonian-connected tournament structures were researched by Thomasson ^[30]. Adequate conditions for graphs to possess Hamilton-connectedness structure were studied by Kewen et al. ^[18]. Zhou et al. ^[40] established Hamilton-connectivity conditions based on signless Laplacian spectral radius, adjacency spectral radius, and edge count. The Harary and Wiener topological invariants of large-diametrical Hamilonian-connected graphs were computed by Zhou et al. ^[42]. A spectral analogy of Erdös' theorems was explored by Wei et al. ^[36] for Hamiltonian-connected graphs. The alphabet-grid graph and its Hamilton-connectivity was investigated by Hung et al. ^[16]. An extension of Nikiforov and Fiedler's results was derived by Zhou et al. ^[41] who considered Hamiltonian-connected graphs to have sufficiently-large smallest valency and put forward a spectral condition with respect to the signless Laplacian matrix. Network coherence is studied by Liu et al. ^[23] for $2^p$-tree networks.

Convex polytopes' graphs are constructed by retaining the vertex-vertex adjacency as well as vertex-edge incidence relations. Bača ^[2,3,4] is among the first mathematician to study these geometric graphs. Bača in ^[4] and ^[3] investigated convex polytopes for their magic labeling, as well as graceful and anti-graceful labeling. Later, in ^[2], his focus was shifted to anti-magic face labeling. Imran et al. ^[17] determined the exact value of the metric dimension for several classes of convex polytopes and classified it as constant. Raza et al. ^[27] and Raza et al. ^[28] explored the fault-tolerance and vertex-edge resolvability in convex polytopes, respectively. Raza et al. ^[26] and Simić et al. ^[29] computed exact values of the locating-domination number of some classes of convex polytopes and established tight bounds for some other families.

1.1.   The detour index

In structure-property modeling, Lukovits ^[20] presented a strong applicability of the detour index in chemistry. Trinajstić et al. ^[33] expanded on the detour index's applications to the Wiener index by conducting a comparative test, assessing its usefulness in predicting the boiling points of hydrocarbons and organic compounds. Additionally, Rücker and Rücker ^[25] employed the detour index to forecast the boiling points in alkanes.

Lukovits et al. ^[22] introduced an algorithm for tracing detours between two vertices in a graph and applied it to compute its detour indices representing fused bicyclic skeletons. Furthermore, Rücker et al. ^[25] and Trinajstić et al. ^[32] developed computational methods for identifying detours and calculating the detour index of graphs. It is noted in ^[14] that determining a graph's detour index is an NP-complete problem. Trinajstić et al. ^[32] put forward a computational method for the detour matrix for graphs of manageable size, where the detour index is from the detour matrix. The computational complexity of the longest path problem has been investigated by Fomin et al. ^[10].

Determining whether a graph is Hamilton-connected or calculating its detour index are known to be NP-complete problems ^[11,14]. Due to this complexity, it is natural to focus on these problems for specific graph families. Here, we investigate the Hamilton-connectivity of certain infinite families of convex polytopes. We also generate certain families of Hamilton-connected convex polytopes and employ two distinct proof techniques to establish our results. Notably, we correct a significant error made by Hayat et al. ^[15], who incorrectly claimed that the convex polytope $B_ \varepsilon$ is not Hamilton-connected, whereas we prove that the family $B_ \varepsilon$ is indeed Hamilton-connected.

Next, we remark on the computational complexity of the longest path problem above the diameter.

Theorem 1.1. The problem of the Longest Path above Diameter is NP-complete.

Proof. Let $G$ be a graph with $n \ge 2$ vertices. We construct graph $G'$ as follows (see Figure 1):

● Construct a copy of $G$.

● Construct a vertex $u$ and make it adjacent to every vertex of the copy of $G$.

● Construct two vertices $s$ and $t$, and then $(s, u)$ and $(u, t)$ paths $P_s$ and $P_t$, respectively, of length $n \ge 1$.

Notice that $\mathrm{diam}(G) = \mathrm{length}(P_s) + \mathrm{length}(P_t) = 2n-2$. It is easy to verify that $G'$ has a path of length $2n-1$ if and only if $G$ has a path of length $n-1$, that is, $G$ is Hamiltonian. Because the Hamiltonian path is well-known to be NP-complete ^[11], we conclude that the Longest Path above Diameter is NP-complete. □

2.   Preliminaries

A graph $\Omega$ is defined as an ordered pair $\Omega = \big(V(\Omega), E(\Omega)\big)$, where $V(\Omega)$ represents the vertex set (i.e., a set of points called vertices) and $E(\Omega)\subseteq{V(\Omega)\choose2}$ denotes the edge set (i.e., a set of lines connecting the points, known as edges). The number of vertices, denoted by $\varepsilon: = |V(\Omega)|$, is referred to as the order of $\Omega$. For two vertices $y, z\in V(\Omega)$, the notation $y\sim z$ indicates that $y$ and $z$ are adjacent, meaning they are connected by an edge. For a subset $Y\subseteq V(\Omega)$ and vertices $w, x\in V(\Omega)$, if $Z = {z_i:1\leq i\leq p}$, then $w\sim {z_i:1\leq i\leq p}\sim x$ signifies that $w\sim z_1$ and $z_p\sim x$, while the adjacency between the intermediate vertices $z_i$ $(2\leq i\leq p)$ remains unchanged. For a positive integer $\varepsilon \in\mathbb{Z}^+$, we use $\varepsilon \mid2$ (respectively, $\varepsilon \nmid2$) to indicate that $\varepsilon$ is even (respectively, odd).

A cycle in a graph $\Omega$ is called Hamiltonian if it passes through all vertices of $\Omega$ exactly once. Similarly, a path in $\Omega$ is referred to as a Hamiltonian path if it visits every vertex in the graph. Not all graphs contain a Hamiltonian cycle; for instance, any tree is acyclic and therefore cannot have a Hamiltonian cycle, although it may contain a Hamiltonian path. A graph $\Omega$ is considered Hamiltonian if it possesses a Hamiltonian cycle. By definition, cycle graphs and clique graphs are Hamiltonian. A graph is said to be traceable if it has a Hamiltonian path. While every Hamiltonian graph is traceable, some traceable graphs are not Hamiltonian. A classic example is the Petersen graph, which contains a Hamiltonian path but lacks a Hamiltonian cycle. A graph is defined as Hamilton-connected if there is a Hamiltonian path between every pair of vertices in $\Omega$.

Let $\Omega$ be a graph. A subset $S\subseteq V(\Omega)$ (resp. $T\subseteq E(\Omega)$) is called a vertex-cut (resp. edge-cut) if removing $S$ (resp. $T$) from $\Omega$ results in a graph with more than one connected component. A vertex cut of size 1 corresponds to an articulation vertex. The vertex connectivity $\kappa(\Omega)$ (resp. edge connectivity $\lambda(\Omega)$) is defined as the minimum cardinality of a vertex-cut (resp. edge-cut) in $\Omega$. A graph is said to be $k$-vertex-connected (resp. $k$-edge-connected) if its vertex-connectivity (resp. edge-connectivity) is greater than or equal to a fixed number $k$. In other words, a graph is $k$-vertex-connected or simply $k$-connected if there is no vertex-cut of cardinality $k-1$ in $\Omega$.

Let $\delta(\Omega)$ be the minimum degree of $\Omega$. Whitney ^[35] in 1932 showed the following result:

Theorem 2.1. ^[35] For any graph $\Omega$, the following inequalities hold:

The following well-known Kužel-Xiong Theorem was shown by Kužel in his Ph.D. thesis ^[19].

Theorem 2.2. ^[19] Every $4$-connected line graph is Hamiltonian if and only if it is Hamilton-connected.

Beineke ^[5] independently gave the following characterization of line graphs.

Theorem 2.3. The following statement are equivalent for a graph $\Omega$:

$(i)$ $\Omega$ is the line graph of some graph.

$(ii)$ The nine graphs in Figure 2 are forbidden in $\Omega$, i.e., none of these graphs can be induced subgraphs of $\Omega$.

See page 47 of Harary's book ^[14] for more information on this characterization.

For a graph $\Omega$, let $\delta(x, y)$ represent the length of the longest path (i.e., detour) between vertices $x$ and $y$ in $\Omega$. The detour index ^[21] is defined as the sum of the detours between all unordered pairs of vertices in $\Omega$. The detour index of a graph $\Omega$ is typically denoted by $\omega(\Omega)$.

We end this section with an important and well-known result bounding the detour index in terms of graph parameters.

Theorem 2.4. ^[8] Let $\Omega$ be an $n$-vertex graph with $n\geq 3$ and $\omega(\Omega)$ be its detour index. Then

with left equality holds if and only if $\Omega$ is Hamilton-connected, and right inequality holds if and only if $\Omega\cong S_{n}$.

3.   Hamilton-connectivity and the detour index of $E_ \varepsilon$

In this section, we introduce a novel family of convex polytopes called the convex polytope $E_ \varepsilon$ of dimension $\varepsilon$. Here, we aim to prove Hamilton-connectedness of $E_ \varepsilon$ and employ it to evaluate its detour index.

Assuming the subscript $r$ to be modulo $\varepsilon$, the vertex/edge sets for $E_ \varepsilon$ are:

With its vertices' labeling, Figure 3 delivers the construction of $E_ \varepsilon$. For our proofs, we define panels 1, 2, and 3 to comprise the vertices $a_r$, $b_r$, and $c_r$, respectively.

The next theorem delivers the main result of this section. The proof technique employs Theorem 2.2 by Kužel and Xiong ^[19], which asserts that a 4-connected Hamiltonian line graph is Hamilton-connected. Thus, we divide our proof for $\Omega$ in three steps: (1) $\Omega$ is a line graph; (2) $\Omega$ is 4-connected; and (3) $\Omega$ is Hamiltonian.

Theorem 3.1. If $\varepsilon\geq5$, then $E_ \varepsilon$ is Hamilton-connected.

Proof. Let $\Omega$ be the $\varepsilon$-dimensional convex polytope $E_ \varepsilon$. We divide the proof into a number of claims.

Claim 1: $\Omega$ is a line graph.

Note that $\Omega$ does not contain any of the nine forbidden subgraphs in Figure 2. Thus, by Theorem 2.3, $\Omega$ is a line graph. Moreover, it can be seen that $E_ \varepsilon$ is the line graph of prism graph $C_ \varepsilon\times P_2$, which is also a family of convex polytopes (see Section 1).

Claim 2: For $\varepsilon\geq5$, $\Omega$ is a 4-connected, i.e., $\kappa(\Omega) = 4$.

Note that $\Omega$ is a $4$-regular graph. For $z \in V(\Omega)$, let $S = N_{ \Omega}(z) = \{z_1, z_2, z_3, z_4\}$ represent the neighborhood of $z$ in $\Omega$. Observe that $V \setminus \Omega$ is disconnected, with $z$ as an isolated connected component. This implies that $\kappa(\Omega) \leq 4$. To demonstrate that $\kappa(\Omega) \geq 4$, let $S = \{v, w, x\}$ be a subset of $V(\Omega)$, where $v$, $w$, and $x$ are arbitrary vertices. We show that deleting $S$ from $\Omega$ leaves the graph connected.

Here, we divide our discussion into a number of cases.

Case 1. Panels 1 or 3 of $\Omega$ comprise all three vertices of $S$.

In panels 1 or 3, the vertices $v$, $w$, and $x$ may be arranged as either consecutive vertices, two adjacent vertices with one non-adjacent, or all three being non-adjacent. If $v$, $w$, and $x$ are positioned in panel 1, their neighbors will be found in panels 1 and 2. Conversely, if they are in panel 3, the neighboring vertices will be in panels 2 and 3. In every situation, these neighboring vertices exhibit degrees of either two or three in the graph $\Omega - S$. This demonstrates that $S$ does not constitute a vertex cut set for $\Omega$, as the graph $\Omega - S$ continues to be connected.

Case 2. All three vertices of $S$ are situated in panel 2 of $\Omega$.

In panel 2, the vertices $v$, $w$, and $x$ can be either consecutive or non-consecutive. Regardless of their arrangement, the neighboring vertices are in panels 1 and 3 if they are part of panel 2. All neighboring vertices in panels 1 or 3 have degrees of either 2 or 3 in $\Omega - S$. Examining the structure of $\Omega$ as shown in Figure 3, it is evident that $S$ does not serve as a vertex cut set for $\Omega$, since $\Omega - S$ remains connected.

Case 3. Two vertices of $S$ are positioned in either panel 1 or panel 3, and the remaining vertex is in panel 2.

If all three vertices of $S$ are adjacent, forming a triangle, then the neighbors of $v$, $w$, and $x$ are found in panels 1, 2, or 3 of $\Omega$, each having degrees of either 2 or 3 in $\Omega - S$. Additionally, if the two vertices in panel 1 or 3 are adjacent while the vertex in panel 2 is non-adjacent to the other two vertices of $S$, the neighbors of $v$, $w$, and $x$ will also belong to panels 1, 2, or 3, maintaining degrees of either 2 or 3 in $\Omega - S$. Last, if the two vertices in panel 1 or 3 are non-adjacent, the number of neighbors for $v$, $w$, and $x$ increases, with these neighbors still having degrees of either 2 or 3 in $\Omega - S$. Therefore, as shown in Figure 3, $S$ does not constitute a vertex cut set in this scenario either, since $\Omega - S$ remains connected.

Case 4. Two vertices of $S$ are situated in panel 2, while the third vertex is located in either panel 1 or panel 3.

This scenario is quite straightforward since the two vertices in panel 2 cannot be adjacent. Consequently, all neighbors of $v$, $w$, and $x$ are present in panels 1, 2, and 3, irrespective of whether the remaining vertex is in panel 1 or panel 3. Each of these neighbors has a degree of at least 2, indicating that $S$ does not function as a vertex cut set for $\Omega$, as $\Omega - S$ remains connected.

Case 5. Each vertex of $S$ is located in a different panel in $\Omega$.

Applying the same reasoning as in the previous cases, we conclude that $\Omega - S$ remains connected in this scenario as well.

By integrating our findings from Cases 1–5, we determine that no set of three vertices in $\Omega$ can serve as a vertex cut set. This establishes that $\kappa(\Omega) \geq 4$. When combined with the result $\kappa(\Omega) \leq 4$, this completes the proof of Claim 2.

Claim 3: $\Omega$ is a Hamiltonian.

The following is the Hamiltonian cycle in $\Omega$:

Claims 1–3 show that $\Omega$ is a family of Hamiltonian, 4-connected line graphs. By using Theorem 2.2, $\Omega$ is Hamilton-connected. □

Note that $|V(E_ \varepsilon)| = 3 \varepsilon$. Theorems 2.4 and 3.1, together with $|V(E_ \varepsilon)| = 3 \varepsilon$, deliver the following corollary:

Corollary 3.1. Assuming $\varepsilon\geq5$, we have

Proof. Since $|V(E_ \varepsilon)| = 3 \varepsilon$. Theorem 2.4 with $n = 3 \varepsilon$ finishes the proof. □

4.   Hamilton-connectivity and the detour index of $Q_ \varepsilon$

In this section, we explore Hamilton-connectivity of the convex polytope $Q_ \varepsilon$ of dimension $\varepsilon$. It was introduced by Bača ^[3] in 1988. We, in this section, aim to prove Hamilton-connectedness of $Q_ \varepsilon$ and employ it to evaluate its detour index.

Assuming the subscript $r$ to be modulo $\varepsilon$, the vertex/edge sets for $Q_ \varepsilon$ are:

With its vertices' labeling, Figure 4 delivers the construction of $Q_ \varepsilon$.

Here, we prove the main result, asserting that $Q_ \varepsilon$ is Hamilton-connected. The proof technique utilizes the methodology of Alspach and Liu ^[1] using the well-known Posa exchange in constructing Hamiltonian paths between every pair of vertices in a graph.

Theorem 4.1. Assuming $\varepsilon\geq6$, the graph $Q_ \varepsilon$ is Hamilton-connected.

Proof. We show the result by constructing pairwise Hamiltonian paths between vertices of $Q_ \varepsilon$. Assume $H_{p}(w, z)$ is a Hamiltonian path between $w, z\in V(Q_ \varepsilon)$. Furthermore, assume $Q_ \varepsilon\ = \ A\cup B\cup C\cup D$ such that $A = \{a_1, a_2, \ldots, a_ \varepsilon\},$ $B = \{b_1, b_2, \ldots, b_ \varepsilon\}$, $C = \{c_1, c_2, \ldots, c_ \varepsilon\}$ and $D = \{d_1, d_2, \ldots, d_ \varepsilon\}$.

Case 1. $w = a_1$ and $z = a_r, \; 2\le r\le \varepsilon$

Subcase 1.1. $r\ = \ 2$

Subcase 1.2. $r\equiv 0(\mod 2),$ $2\ < \ r\ < \ \varepsilon$

Subcase 1.3. $r\equiv 1(\mod 2),$ $2\ < \ r\ < \ \varepsilon-1$

Subcase 1.4. $r = \varepsilon-1$, and $\varepsilon\equiv 0(\mod 2)$

Subcase 1.5. $r\ = \ \varepsilon$

Case 2. $w = a_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 2.1. $r\ = \ 1$

Subcase 2.2. $r\equiv 0(\mod 2),$ $2\ \le \ r\ < \ \varepsilon$

Subcase 2.3. $r\equiv 1(\mod 2),$ $2\ < \ r\ < \ \varepsilon -1$

Subcase 2.4. $r = \varepsilon -1$, and $\varepsilon \equiv 0(\mod 2)$

Subcase 2.5. $r\ = \ \varepsilon$

Case 3. $w = a_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 3.1. $r\ = \ 1$

Subcase 3.2. $r\ = \ 2$

Subcase 3.3. $r\ = \ 3$

Subcase 3.4. $r\equiv 0(\mod 2),$ $3\ < \ r\ < \ \varepsilon -1$

Subcase 3.5. $r\equiv 1(\mod 2),$ $3\ < \ r\ < \ \varepsilon -1$

Subcase 3.6. $r\ = \ \varepsilon -1$

Subcase 3.7. $r\ = \ \varepsilon$

Case 4. $w = a_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 4.1. $r\ = \ 1$

Subcase 4.2. $r\ = \ 2$

Subcase 4.3. $r\ = \ 3$

Subcase 4.4. $r\equiv 0(\mod 2),$ $3\ < \ r\ < \ \varepsilon$

Subcase 4.5. $r\equiv 1(\mod 2),$ $3\ < \ r\ < \ \varepsilon$

Subcase 4.6. $r\ = \ \varepsilon$

Case 5. $w = b_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 5.1. $r\ = \ 1$

Subcase 5.2. $r\ = \ 2$

Subcase 5.3. $r\equiv 0(\mod 2),$ $2\ < \ r\ < \ \varepsilon -1$

Subcase 5.4. $r\equiv 1(\mod 2),$ $2\ < \ r\ < \ \varepsilon -1$

Subcase 5.5. $r\ = \ \varepsilon -1$

Subcase 5.6. $r\ = \ \varepsilon$

Case 6. $w = b_1$ and $z = b_r, 2\le r\le \varepsilon$

Subcase 6.1. $r\ = \ 2,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 6.2. $r\ = \ 2,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 6.3. $r\ = \ 3$

Subcase 6.4. $r\equiv 0(\mod 2),$ $3\ < \ r\ < \ \varepsilon$

Subcase 6.5. $r\equiv 1(\mod 2),$ $3\ < \ r\ < \ \varepsilon$

Subcase 6.6. $r\ = \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 6.7. $r\ = \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Case 7. $w = b_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 7.1. $r\ = \ 1$

Subcase 7.2. $r\ = \ 2$

Subcase 7.3. $r\equiv 0(\mod 2), \ \ 2\ < \ r\ < \ \varepsilon -1,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 7.4. $r\equiv 1(\mod 2), \ \ 2\ < \ r\ < \ \varepsilon -1,$ and $\varepsilon \equiv 0(\mod 2)\ $

Subcase 7.5. $r\equiv 0(\mod 2), \ \ 2\ < \ r\ < \ \varepsilon -1,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 7.6. $r\equiv 1(\mod 2), \ \ 2\ < \ r\ < \ \varepsilon -1,$ and $\varepsilon \equiv 1(\mod 2)\ $

Subcase 7.7. $r\ = \ \varepsilon -1$

Subcase 7.8. $r\ = \ \varepsilon$

Case 8. $w = b_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 8.1. $r\ = \ 1$, $\varepsilon \equiv 0(\mod 2)$

Subcase 8.2. $r\ = \ 1$, $\varepsilon \equiv 1(\mod 2)$

Subcase 8.3. $r\ = \ 2$

Subcase 8.4. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 8.5. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 8.6. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 8.7. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 8.8. $r\ = \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 8.9. $r\ = \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Case 9. $w = c_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 9.1. $r\ = \ 1$

Subcase 9.2. $r\ = \ 2$

Subcase 9.3. $r\ = \ 3$

Subcase 9.4. $r\equiv 0(\mod 2), \ 3\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 9.5. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 9.6. $r\equiv 0(\mod 2), \ 3\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 9.7. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 9.8. $r\ = \ \varepsilon$

Case 10. $w = c_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 10.1. $r\ = \ 1$

Subcase 10.2. $r\ = \ 2$

Subcase 10.3. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 10.4. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 10.5. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 10.6. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 10.7. $\ r\ = \ \varepsilon$

Case 11. $w = c_1$ and $z = c_r, 2\le r\le \varepsilon$

Subcase 11.1. $r\ = \ 2$

Subcase 11.2. $r\ = \ 3$

Subcase 11.3. $r\equiv 0(\mod 2),$ $2\ < \ r\ < \ \varepsilon$

Subcase 11.4. $r\equiv 1(\mod 2),$ $3\ < \ r\ < \ \varepsilon$

Subcase 11.5. $r\ = \ \varepsilon -1,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 11.6. $r\ = \ \varepsilon -1,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 11.7. $r\ = \ \varepsilon$

Case 12. $w = c_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 12.1. $r\ = \ 1$

Subcase 12.2. $r\ = \ 2$

Subcase 12.3. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon, \ $and $\varepsilon \equiv 0(\mod 2)\ $

Subcase 12.4. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 12.5. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 12.6. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 12.7. $r\ = \ \varepsilon$

Case 13. $w = d_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 13.1. $r\ = \ 1$

Subcase 13.2. $r\ = \ 3$

Subcase 13.3. $r\equiv 0(\mod 2)$

Subcase 13.4. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 13.5. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 13.6. $r\ = \ \varepsilon$

Case 14. $w = d_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 14.1. $r\ = \ 1,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 14.2. $r\ = \ 1,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 14.3. $r\ = \ 2,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 14.4. $r\ = \ 2,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 14.5. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon, \ $and $\varepsilon \equiv 0(\mod 2)$

Subcase 14.6. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 14.7. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 14.8. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 14.9. $r\ = \ \varepsilon$

Case 15. $w = d_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 15.1. $r\ = \ 1$

Subcase 15.2. $r\ = \ 2$

Subcase 15.3. $r\ = \ 3$

Subcase 15.4. $r\equiv 0(\mod 2), \ 3\ < \ r\ < \ \varepsilon$

Subcase 15.5. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon$

Subcase 15.6. $r\ = \ \varepsilon$

Case 16. $w = d_1$ and $z = d_r, 2\le r\le \varepsilon$

Subcase 16.1. $r\ = \ 2$

Subcase 16.2. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon -1$

Subcase 16.3. $r\equiv 1(\mod 2),$ $2\ < \ r\ < \ \varepsilon -1,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 16.4. $r\equiv 1(\mod 2),$ $2\ < \ r\ < \ \varepsilon -1,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 16.5. $r\ = \ \varepsilon -1,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 16.6. $r\ = \ \varepsilon -1,$ and $\varepsilon \equiv 1(\mod 2)$

Subcase 16.7. $r\ = \ \varepsilon$

Existence of Hamiltonian path between any two vertices of the $Q_ \varepsilon$ completes the proof. □

Having $|V(Q_ \varepsilon)| = 4 \varepsilon$, Theorems 2.4 and 4.1 deliver the following immediate result:

Corollary 4.1. Assuming $\varepsilon\geq6$, we have

Proof. Since $|V(Q_ \varepsilon)| = 4 \varepsilon$. Theorem 2.4 with $n = 4 \varepsilon$ delivers the formula in the corollary. □

5.   Hamilton-connectivity and the detour index of $B_ \varepsilon$

In this section, we explore Hamilton-connectivity of the convex polytope $B_ \varepsilon$ of dimension $\varepsilon$, which was introduced by Imran et al. ^[17] in 2016. We, in this section, aim to prove Hamilton-connectedness of $B_ \varepsilon$ and employ it to evaluate its detour index.

Assuming the subscript $r$ to be modulo $\varepsilon$, the vertex/edge sets for $B_ \varepsilon$ are:

With its vertices' labeling, Figure 5 delivers the construction of $B_ \varepsilon$.

Note that Hayat et al. [15, Thereom 5] showed the following result:

Theorem 5.1. [15, Thereom 5] Considering $\varepsilon \ge 4$, the graph $B_\in$ is not Hamilton-connected.

They show in the proof that there is no Hamiltonian path between $e_r$ and $e_{r+1}$ if $\varepsilon$ is odd. We show that their proof was wrong and there are multiple Hamiltonian paths between $e_r$ and $e_{r+1}$ if $\varepsilon$ is odd. Correcting their proof, we show that the graph $B_\in$ is, in fact, Hamilton-connected.

Next, we show this section's major results, delivering the proof for Hamilton-connectivity of $B_ \varepsilon$. The proof technique utilizes the methodology of Alspach and Liu ^[1] using the well-known Posa exchange in constructing Hamiltonian paths between every pair of vertices in a graph.

Theorem 5.2. If $\varepsilon\geq6$, then $B_ \varepsilon$ is, in fact, Hamilton-connected.

Proof. We show the result by constructing pairwise Hamiltonian paths between vertices of $Q_ \varepsilon$. Assume $H_{p}(w, z)$ is a Hamiltonian path between $w, z\in V(Q_ \varepsilon)$. Let $B_ \varepsilon\ = \ A\cup B\cup C\cup D\cup E$ where $A = \{a_1, a_2, \ldots, a_ \varepsilon \},$ $B = \{b_1, b_2, \ldots, b_ \varepsilon \}$, $C = \{c_1, c_2, \ldots, c_ \varepsilon \}$, $D = \{d_1, d_2, \ldots, d_ \varepsilon \}$, and $E = \{e_1, e_2, \ldots, e_ \varepsilon\}$.

Case 1. $w = a_1$ and $z = a_r, 2\le r\le \varepsilon$

Subcase 1.1. $r\ = \ 2$

Subcase 1.2. $r\equiv 0(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 1.3. $r\equiv 1(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 1.4. $r = \varepsilon -1$

Subcase 1.5. $r\ = \ \varepsilon$

Case 2. $w = a_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 2.1. $r\ = \ 1$

Subcase 2.2. $r\ = \ 2$

Subcase 2.3. $r\equiv 0(\mod 2),$ and $2\ \le \ r\ < \ \varepsilon -1$

Subcase 2.4. $r\equiv 1(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 2.5. $r\ = \ \varepsilon -1$

Subcase 2.6. $r\ = \ \varepsilon$

Case 3. $w = a_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 3.1. $r\ = \ 1$

Subcase 3.2. $r\ = \ 2$

Subcase 3.3. $r\equiv 0(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 3.4. $r\equiv 1(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 3.5. $r\ = \ \varepsilon -1$

Subcase 3.6. $r\ = \ \varepsilon$

Case 4. $w = a_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 4.1. $r\ = \ 1$

Subcase 4.2. $r\ = \ 2$

Subcase 4.3. $r\equiv 0(\mod 2),$ and $2\ < \ r\ < \ \varepsilon$

Subcase 4.4. $r\equiv 1(\mod 2),$ and $3\ < \ r\ < \ \varepsilon$

Subcase 4.5. $r\ = \ \varepsilon$

Case 5. $w = a_1$ and $z = e_r, 1\le r\le \varepsilon$

Subcase 5.1. $r\ = \ 1$

Subcase 5.2. $r\ = \ 2$

Subcase 5.3. $r\equiv 0(\mod 2),$ and $2\ < \ r\ < \ \varepsilon$

Subcase 5.4. $r\equiv 1(\mod 2),$ and $2\ < \ r\ < \ \varepsilon$

Subcase 5.5. $r\ = \ \varepsilon$

Case 6. $w = b_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 6.1. $r\ = \ 1$

Subcase 6.2. $r\ = \ 2$

Subcase 6.3. $r\equiv 0(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 6.4. $r\equiv 1(\mod 2),$ and $2\ < \ r\ < \ \varepsilon -1$

Subcase 6.5. $r\ = \ \varepsilon -1$

Subcase 6.6. $r\ = \ \varepsilon$

Case 7. $w = b_1$ and $z = b_r, 2\le r\le \varepsilon$

Subcase 7.1. $r\ = \ 2$

Subcase 7.2. $r\ = \ 3$

Subcase 7.3. $r\equiv 0(\mod 2),$ and $3\ < \ r\ < \ \varepsilon$

Subcase 7.4. $r\equiv 1(\mod 2),$ and $3\ < \ r\ < \ \varepsilon$

Subcase 7.5. $r\ = \ \varepsilon$

Case 8. $w = b_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 8.1. $r\ = \ 1$

Subcase 8.2. $r\ = \ 2$

Subcase 8.3. $r\ = \ 3$

Subcase 8.4. $r\equiv 0(\mod 2), \ \ 3\ < \ r\ < \ \varepsilon -1$

Subcase 8.5. $r\equiv 1(\mod 2), \ \ 3\ < \ r\ < \ \varepsilon -1$

Subcase 8.6. $r\ = \ \varepsilon -1$

Subcase 8.7. $r\ = \ \varepsilon$

Case 9. $w = b_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 9.1. $r\ = \ 1$, $\varepsilon \equiv 0(\mod 2)$

Subcase 9.2. $r\ = \ 1$, $\varepsilon \equiv 1(\mod 2)$

Subcase 9.3. $r\ = \ 2$

Subcase 9.4. $r\ = \ 3$

Subcase 9.5. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 9.6. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 9.7. $r\ = \ \varepsilon,$ and $\varepsilon \equiv 0(\mod 2)$

Subcase 9.8. $r\ = \ \varepsilon,$ and $\varepsilon \equiv 1(\mod 2)$

Case 10. $w = b_1$ and $z = e_r, 1\le r\le \varepsilon$

Subcase 10.1. $r\ = \ 1$

Subcase 10.2. $r\ = \ 2$

Subcase 10.3. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon -1$

Subcase 10.4. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon -1$

Subcase 10.5. $r\ = \ \varepsilon -1$

Subcase 10.6. $r\ = \ \varepsilon$ and $\varepsilon \equiv 1(\mod 2)$

Case 11. $w = c_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 11.1. $r\ = \ 1$

Subcase 11.2. $r\ = \ 2$

Subcase 11.3. $r\ = \ 3$

Subcase 11.4. $r\equiv 0(\mod 2), \ 3\ < \ r\ < \ \varepsilon -1$

Subcase 11.5. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon -1$

Subcase 11.6. $r\ = \ \varepsilon -1$

Subcase 11.7. $r\ = \ \varepsilon$

Case 12. $w = c_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 12.1. $r\ = \ 1$

Subcase 12.2. $r\ = \ 2$

Subcase 12.3. $r\ = \ 3$

Subcase 12.4. $r\equiv 0(\mod 2), \ 3\ < \ r\ < \ \varepsilon$

Subcase 12.5. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon$

Subcase 12.6. $r\ = \ \varepsilon$

Case 13. $w = c_1$ and $z = c_r, 2\le r\le \varepsilon$

Subcase 13.1. $r\ = \ 2$

Subcase 13.2. $r\ = \ 3$

Subcase 13.3. $r\equiv 0(\mod 2),$ and $3\ < \ r\ < \ \varepsilon$

Subcase 13.4. $r\equiv 1(\mod 2),$ and $3\ < \ r\ < \ \varepsilon$

Subcase 13.5. $r\ = \ \varepsilon -1$

Subcase 13.6. $r\ = \ \varepsilon$

Case 14. $w = c_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 14.1. $r\ = \ 1$

Subcase 14.2. $r\ = \ 2$

Subcase 14.3. $r\ = \ 3$

Subcase 14.4. $r\equiv 0(\mod 2), \ 3\ < \ r\ < \ \varepsilon -1$

Subcase 14.5. $r\equiv 1(\mod 2), \ 3\ < \ r\ < \ \varepsilon -1$

Subcase 14.6. $r\ = \ \varepsilon -1$

Subcase 14.7. $r\ = \ \varepsilon$

Case 15. $w = c_1$ and $z = e_r, 1\le r\le \varepsilon$

Subcase 15.1. $r\ = \ 1$

Subcase 15.2. $r\equiv 0(\mod 2)$

Subcase 15.3. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 15.4. $r\ = \ \varepsilon$

Case 16. $w = d_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 16.1. $r\ = \ 1$

Subcase 16.2. $r\equiv 0(\mod 2), \ 1\ < \ r\ < \ \varepsilon -1$

Subcase 16.3. $r\equiv 1(\mod 2), \ 1\ < \ r\ < \ \varepsilon -1$

Subcase 16.4. $r\ = \ \varepsilon -1$

Subcase 16.5. $r\ = \ \varepsilon$

Case 17. $w = d_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 17.1. $r\ = \ 1, \ \varepsilon \equiv 0(\mod 2)$

Subcase 17.2. $r\ = \ 1, \ \varepsilon \equiv 1(\mod 2)$

Subcase 17.3. $r\ = \ 2, \ \varepsilon \equiv 0(\mod 2)$

Subcase 17.4. $r\ = \ 2, \ \varepsilon \equiv 1(\mod 2)$

Subcase 17.5. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 17.6. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 17.7. $r\ = \ \varepsilon$

Case 18. $w = d_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 18.1. $r\ = \ 1$

Subcase 18.2. $r\ = \ 2$

Subcase 18.3. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 18.4. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 18.5. $r\ = \ \varepsilon$

Case 19. $w = d_1$ and $z = d_r, 2\le r\le \varepsilon$

Subcase 19.1. $r\ = \ 2$

Subcase 19.2. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon$

Subcase 19.3. $r\equiv 1(\mod 2), \ \varepsilon \equiv 0(\mod 2), 2\ < \ r\ < \ \ \varepsilon -1$

Subcase 19.4. $r\equiv 1(\mod 2), \ \varepsilon \equiv 1 (\mod 2), 2\ < \ r\ < \ \ \varepsilon -1$

Subcase 19.5. $r\ = \ \varepsilon -1, \ \varepsilon \equiv 0 (\mod 2)$

Subcase 19.6. $r\ = \ \varepsilon$

Case 20. $w = d_1$ and $z = e_r, 1\le r\le \varepsilon$

Subcase 20.1. $r\ = \ 1$

Subcase 20.2. $r\ = \ 2$

Subcase 20.3. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon -1$

Subcase 20.4. $r\equiv 1(\mod 2), 2\ < \ r\ < \ \ \varepsilon -1$

Subcase 20.5. $r\ = \ \varepsilon -1$

Subcase 20.6. $r\ = \ \varepsilon$

Case 21. $w = e_1$ and $z = a_r, 1\le r\le \varepsilon$

Subcase 21.1. $r\ = \ 1$

Subcase 21.2. $r\equiv 0(\mod 2), \ 1\ < \ r\ < \ \varepsilon$

Subcase 21.3. $r\equiv 1(\mod 2), \ 1\ < \ r\ < \ \varepsilon$

Subcase 21.4. $r\ = \ \varepsilon -1$

Subcase 21.5. $r\ = \ \varepsilon$

Case 22. $w = e_1$ and $z = b_r, 1\le r\le \varepsilon$

Subcase 22.1. $r\ = \ 1$

Subcase 22.2. $r\equiv 0(\mod 2), \ 1\ < \ r\ < \ \varepsilon$

Subcase 22.3. $r\equiv 1(\mod 2), \ 1\ < \ r\ < \ \varepsilon$

Subcase 22.4. $r\ = \ \varepsilon -1$

Subcase 22.5. $r\ = \ \varepsilon$

Case 23. $w = e_1$ and $z = c_r, 1\le r\le \varepsilon$

Subcase 23.1. $r\ = \ 1$

Subcase 23.2. $r\ = \ 2$

Subcase 23.3. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \varepsilon -1$

Subcase 23.4. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \varepsilon -1$

Subcase 23.5. $r\ = \ \varepsilon -1$

Subcase 23.6. $r\ = \ \varepsilon$

Case 24. $w = e_1$ and $z = d_r, 1\le r\le \varepsilon$

Subcase 24.1. $r\ = \ 1$

Subcase 24.2. $r\ = \ 2, \ \varepsilon \equiv 0(\mod 2)$

Subcase 24.3. $r\ = \ 2, \ \varepsilon \equiv 1(\mod 2)$

Subcase 24.4. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \ \varepsilon$

Subcase 24.5. $r\equiv 1(\mod 2), \ 2\ < \ r\ < \ \ \varepsilon$

Subcase 24.6. $r\ = \ \varepsilon, \ \varepsilon \equiv 0 (\mod 2)$

Subcase 24.7. $r\ = \ \varepsilon, \varepsilon \equiv 1 (\mod 2)$

Case 25. $w = e_1$ and $z = e_r, 1\le r\le \varepsilon$

Subcase 25.1. $r\ = \ 2$

Subcase 25.2. $r\equiv 0(\mod 2), \ 2\ < \ r\ < \ \ \varepsilon -1$

Subcase 25.3. $r\equiv 1(\mod 2), \ \varepsilon \equiv 0 (\mod 2), \ 2\ < \ r\ < \ \ \varepsilon -1$

Subcase 25.4. $r\equiv 1(\mod 2), \ \varepsilon \equiv 1 (\mod 2), \ 2\ < \ r\ < \ \ \varepsilon -1$

Subcase 25.5. $r\ = \ \varepsilon -1$

Subcase 25.6. $r\ = \ \varepsilon$

Existence of Hamiltonian path between any two vertices of the $B_ \varepsilon$ completes the proof. □

Note that $|V(B_ \varepsilon)| = 4 \varepsilon$. Using it with Theorems 2.4 and 5.2 deliver the following immediate result:

Corollary 5.1. Assuming $\varepsilon\geq6$, we have

Proof. Since $|V(B_ \varepsilon)| = 4 \varepsilon$. Theorem 2.4 with $n = 4 \varepsilon$ delivers the result. □

6.   Conclusions

Contributions

● Introduced two distinct methods for proving Hamilton-connectedness of convex polytopes.

● Constructed three infinite families of Hamilton-connected convex polytopes.

● Corrected a misconception regarding the Hamilton-connectivity of the convex polytope $B_{\varepsilon}$, proving it is Hamilton-connected.

● Provided explicit computation of the detour index for these polytopes, establishing their structural properties.

● Extended previous results on Hamilton-connected graphs to new classes of geometric graphs derived from polytopes.

Implications

● Enhances understanding of Hamilton-connected structures within convex polytopes, contributing to graph theory and computational geometry.

● Provides new techniques for proving Hamilton-connectedness that can be applied to other combinatorial structures.

● Supports applications in network topology, where Hamilton-connected properties ensure robust and efficient routing.

● Offers insights into the relationship between geometric polytopes and their corresponding graph-theoretic properties.

● Strengthens theoretical foundations for detour index computations, aiding applications in cheminformatics and molecular modeling.

Limitations

● We focus on specific families of convex polytopes, leaving open the question of Hamilton-connectedness for other polytope classes.

● Computational complexity of verifying Hamilton-connectedness for arbitrary convex polytopes remains a challenge.

● The results rely on combinatorial proof techniques, which may not be directly extendable to all polyhedral structures.

● No empirical validation or algorithmic implementation is provided for the practical computation of detour indices in large graphs.

Future study

● Extend the proposed techniques to analyze Hamilton-connectedness in other polyhedral graphs beyond the studied families.

● Investigate algorithmic methods for efficiently computing detour indices in large-scale applications.

● Explore potential connections between Hamilton-connected convex polytopes and spectral graph theory.

● Develop computational tools to automate the detection of Hamilton-connected properties in graph representations of polytopes.

● Study the implications of Hamilton-connectedness in higher-dimensional convex polytopes and their applications in optimization and network design.

Author contributions

Sakander Hayat and Bagus Imanda: Conceptualization, Methodology, Validation, Formal analysis, Investigation, Writing–original draft preparation, Writing–review and editing, Visualization; Asad Khan: Formal analysis, Investigation, Writing–original draft preparation, Editing; Mohammed J. F. Alenazi: Methodology, Validation, Resources, Writing–original draft preparation. All authors have read and agreed to the published version of the manuscript.

Use of Generative-AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

S. Hayat was supported by UBD Faculty Research Grants (No. UBD/RSCH/1.4/FICBF(b)/2022/053) and National Natural Science Foundation of China (Grant No. 12250410247). The APC was funded by A. Khan who was sponsored by the Key Laboratory of Philosophy and Social Sciences in Guangdong Province of Maritime Silk Road of Guangzhou University, grant No. GD22TWCXGC15, the National Natural Science Foundation of China grant No. 12250410247, and also by the Ministry of Science and Technology of China, grant No. WGXZ2023054L. M. J. F. Alenazi extends his appreciation to Researcher Supporting Project number (RSPD2025R582), King Saud University, Riyadh, Saudi Arabia.

Conflict of interest

The authors declare that they have no known competing financial interests.