Hamilton-connectedness and Hamilton-laceability of planar geometric graphs with applications

1.   Introduction

All graphs in this paper are simple, loopless, finite and connected. For undefined terminologies, we refer to Section 2.

Hamilton-connected graphs were introduced by Ore ^[20] in 1963. There is an extensive amount of literature available on Hamiltoniancity and Hamilton-connectivity of graphs. Determining whether a graph is Hamiltonian or Hamilton-connected are NP-complete problems ^[10]. Frucht ^[9] studied a canonical representation of trivalent Hamiltonian graphs. Wei ^[32] showed some degree conditions for vertices to possess a Hamiltonian path between them. He further showed that with these degree restrictions if a graph is 3-connected, then it must be Hamilton-connected. Yang et al. ^[35] and Qiang et al. ^[21] independently showed that the generalized honeycomb torus network is Hamiltonian. Gordon et al. ^[11] studied the Hamiltonian properties of triangular grid graphs. Stewart ^[28] proved sufficient conditions for multiswapped networks to be Hamiltonian. Recently, Yang et al. ^[34] found forbidden subetaaphs in super-Eulerian and Hamiltonian graphs.

Chartrand et al. ^[7] showed that the square of a block graph is Hamilton-connected. Thomasson ^[29] studied Hamilton-connected tournaments in graphs. Chang et al. ^[6] studied panconnectivity, fault-tolerant Hamiltonicity and Hamiltonian-connectivity in alternating group graphs by considering them as interconnection networks. Kewen et al. ^[15] derived a sufficient condition for a graph to be Hamilton-connected. Zhou & Wang ^[37] proved certain sufficient conditions for a graph to be Hamilton-connected in terms of the edge number, the spectral radius and the signless Laplacian spectral radius of the graph. Zhou et al. ^[39] calculated the Wiener and Harary indices of Hamilton-connected graphs with large diameter. Wei et al. ^[33] derived some spectral analogues of Erdös' theorems for Hamilton-connected graphs. Hung et al. ^[13] studied Hamilton-connectivity of alphabet grid graphs. Zhou et al. ^[38] extended a result of Fiedler and Nikiforov and derived signless Laplacian spectral conditions for Hamilton-connected graphs with large minimum degree. Recently, Shabbir et al. ^[26] studied Hamilton-connectivity in Teoplitz graphs.

By preserving the vertex-edge incidence relation in convex polytopes, their graphs are constructed. Bača ^[2,3,4] was among the first researchers to consider these families of geometric graphs. In ^[4] (resp. ^[3]), Bača studied the problem of magic (resp. graceful & anti-graceful) labelling of convex polytopes, whereas, in ^[2], the problem of face anti-magic labeling of convex polytopes was studied. Imran et al. ^[14] computed the constant metric dimension of various infinite families of convex polytopes. The fault-tolerant metric dimension (resp. mixed metric dimension) of convex polytopes was studied by Raza et al. ^[24] (resp. Raza et al. ^[25]). The binary locating-dominating number of convex polytopes is studied by Simić et al. ^[27] and Raza et al. ^[23].

1.1.   The detour index

The detour index has important applications in chemistry. Applications of this parameter in quantitative structure activity and property relationship models were put forward by Lukovits ^[17]. Besides giving further applications of the detour index, Trinajstić et al. ^[31] conducted a comparative analysis with the Wiener index in terms of applicability in correlating boiling points of hydrocarbons or, in general, organic compounds. Moreover, its further applications in predicting the normal boiling points of cyclic and acyclic alkanes were studied by Rücker & Rücker ^[22].

An algorithm of tracing the detour between two vertices in a graph was proposed by Lukovits & Razinger ^[19]. They also applied their algorithm in detecting detours and computing the detour index of graphs corresponding to fused bicyclic skeletons. Rücker and Rücker ^[22] and Trinajstić et al. ^[30] proposed certain computer methods to trace out detours and thus calculation of the detour index of graphs. It has already been shown in ^[12] that the problem of finding the detour index of a given graph is computationally NP-complete. Trinajstić et al. ^[30] also proposed a method of calculating the detour matrix of reasonably small sizes. Note that the detour index is equal to the sum of all the entries of the detour matrix dividing by two.

Recall that determining whether or not a graph is Hamilton-connected or computing its detour index are NP-complete problems ^[10,12]. In view of this, it is natural to study these problems for special families of graphs. In this paper, we study the Hamilton-connectedness of certain infinite families of convex polytopes. More precisely, we construct certain infinite families of Hamilton-connected convex polytopes. We have used two different proof techniques to show our results. We also classify the Platonic solids according to their Hamilton-connectedness and Hamilton-laceability properties. By using Hamilton-connectedness of certain families of convex polytopes, we compute exact formulas of their detour index.

2.   Preliminaries

A graph $G$ is an ordered pair $G = \big(V(G), E(G)\big)$ with $V(G)$ as its vertex set (i.e., set of points called vertices) and $E(G)\subseteq{V(G)\choose2}$ as its edge set (i.e., set of lines connecting points called edges). The number of vertices, say $n: = |V(G)|$, is called the order of $G$ and the number of edges, say $m: = |E(G)|$, is called the size of $G$. For two vertices $x, y\in V(G)$, we write $x\sim y$ if both $x$ and $y$ are adjacent i.e., they are connected by an edge. For $U\subseteq V(G)$ and $x, y\in V(G)$, if $U = \{u_i:1\leq i\leq p\}$ then $x\sim \{u_i:1\leq i\leq p\}\sim y$ means that $x\sim u_1$ and $u_p\sim y$ and adjacency in rest of $u_i$'s $(2\leq i\leq p)$ stays the same. For a positive integer $\nu\in\mathbb{Z}^+$, we write $\nu\mid2$ (resp. $\nu\nmid2$) if $\nu$ is even (resp. odd).

A cycle in a graph $G$ is called Hamiltonian if it travels all the vertices of $G$ once. Moreover, a path in $G$ is called Hamiltonian path if it travels all the vertices of $G$. Not every graph contains a Hamiltonian cycle. For instance, any tree is an acyclic graph so it can not contain a Hamiltonian cycle. However, a tress may still contain a Hamiltonian path. A graph $G$ is called Hamiltonian if there exist a Hamiltonian cycle in it. By definition, any cycle graph or a clique graph are Hamiltonian. Furthermore, $G$ is called traceable if it contains a Hamiltonian path. Of course all Hamiltonian graphs are traceable. However, there exist graphs which are traceable but not Hamiltonian. The first non-trivial example which comes in mind immediately is the so-called Petersen graph which is traceable but not Hamiltonian. A graph which contains a Hamiltonian path between every two vertices of $G$ is called Hamilton connected.

Let $G$ be a graph. A subset $S\subseteq V(G)$ (resp. $T\subseteq E(G)$) is said to be a vertex cut (resp. edge cut) if $G-S$ (resp. $G-T$) 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(G)$ (resp. edge connectivity $\lambda(G)$) is the minimum cardinality of a vertex cut (resp. edge cut) in $G$. A graph with vertex connectivity (resp. edge connectivity) greater than or equal to a fixed number say $k$, is said to be $k$-vertex connected (resp. $k$-edge connected). In other words, a graph is $k$-vertex connected or simply $k$-connected if there exists no vertex cut of cardinality $k-1$ in $G$.

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

Theorem 2.1. ^[36] For any graph $G$, the following inequalities hold:

The following well-known Kužel-Xiong Theorem was shown by Kužel in his PhD Thesis ^[16].

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

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

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

(i) $G$ is the line graph of some graph.

(ii) The nine graphs in Figure 1 are forbidden in $G$, i.e., none of these graphs can be induced subetaaphs of $G$.

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

For a graph $G$, let $\ell(x, y)$ be the length of a longest path (i.e., detour) between vertices $x$ and $y$ of $G$. The detour index ^[18] is defined to be the sum of detour between unordered pairs of vertices in $G$. The detour index of a graph $G$ is usually denoted by $\omega(G)$.

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 $G$ be an $n$-vertex graph with $n\geq 3$ and $\omega(G)$ be its detour index. Then

with left equality holds if and only if $G$ is Hamilton-connected, and right inequality holds if and only if $G\cong S_n$.

3.   Hamilton-connectedness and the detour index of $P_n$

In this section, we prove that the Hamilton-connectedness of the convex polytope $P_n$. We use its Hamilton-connectedness to find an exact analytical formula for the detour index of the $P_n$.

The vertex set of $P_n$ is $\{u_i, v_i, w_i, x_i, y_i, z_i:1\leq i\leq n\}$ and the edge set is defined as follows:

where the subscripts are considered modulo $n$. Figure 2 shows the drawing of $P_n$ with proper labeling of vertices. For our purpose, let us call the rows comprising vertices $u_i$ and $w_i$ the layer 1 and layer 2, respectively. In a similar manner, the rows with vertices $v_i$ and $z_i$ form a single layer called layer 3 of $P_n$. The remaining rows containing vertices $y_i$ and $x_i$ are called layer 4 and layer 5, respectively.

Next, we show the main result of this section.

Theorem 3.1. The $n$-dimensional convex polytope $P_n$, with $n\geq5$, is Hamilton-connected.

Proof. Let $G$ be the $n$-dimensional convex polytope $P_n$. We divide the proof into a number of claims.

Claim 1: $G$ is a line graph.

Note that $G$ does not contain any of the nine forbidden subetaaphs Figure 1. So by Theorem 2.3, $G$ is a line graph. Moreover, it can easily be seen that $P_n$ is the line graph of $D_n$ which is also a family of convex polytopes, see Section 1.

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

Note that $G$ is $4$-regular graph. For $v\in V(G)$, let $S = N_{G}(v) = \{v_1, v_2, v_3, v_4\}$ the neighborhood of $v$ in $G$. Note that $V\setminus G$ is disconnected having $v$ as an isolated connected component. This implies that $\kappa(G)\leq 4$. In order to show $\kappa(G)\geq 4$, we let $S = \{a, b, c\}$ to be a subset of $V(G)$, where $a, \; b$ and $c$ are arbitrary vertices and show that deletion of $S$ in $G$ leaves the graph connected.

Here we divide our discussion into a number of cases.

Case 1: All three vertices of $S$ lie either on layer 1, 3 or 5 of $G$.

On layers 1, 3 or 5, the vertices $a, \; b$ and $c$ are either consecutive vertices or two adjacent and one non-adjacent or all three non-adjacent to each other. In each case, if $a, \; b$ and $c$ are on layer 1 (resp. layer 5), then their neighbors are on layers 1 & 2 (resp. layers 4 & 5). Similar If $a, \; b$ and $c$ are on layer 3, their neighboring vertices belong to layers 2, 3 & 4. In every case, these neighboring vertices have degrees either two or three in $G-S$. This implies that $S$ is not a vertex cut set of $G$ as $G-S$ stays connected.

Case 2: All three vertices of $S$ lie either on layer 2 or layer 4 of $G$.

On layer 2 or layer 4, the vertices $a, \; b$ and $c$ are either consecutive or non-consecutive. In each case, the neighboring vertices are on layer 1 & 3 if they belong to layer 2 and on layer 3 & 5 if they belong to layer 4. And all of these neighboring vertices on layer 1, 3 or 5 have degrees either 2 or 3 in $G-S$. By following the structure of $G$ from Figure 2, $S$ is not a vertex cut set of $G$ as $G-S$ stays connected.

Case 3: Two vertices of $S$ lie on one of layers 1, 3 or 5 and one vertex belongs to either layer 2 or 4.

If all three vertices of $S$ are adjacent to each other i.e., they form a triangle, then the neighbors of $a, \; b$ and $c$ belong to layer 1, 3 or 5 or layer 2 & 4 of $G$ having degrees either 2 or 3 in $G-S$. Moreover, if the two vertices of layer 1, 3 or 5 are adjacent and the vertex of the layer 2 or 4 are non-adjacent to the other two vertices of $S$. Then the neighbors of $a, \; b$ and $c$ also belong to either layer 1, 3 & 5 or layer 2 & 4 having degrees either 2 or 3 in $G-S$. The last possibility is that if the two vertices on the layer 1, 3 or 5 are also non-adjacent, then the number of neighbors of $a, \; b$ and $c$ increases having the degrees either 2 or 3 in $G-S$. Thus, Figure 2 implies that $S$ is not a vertex cut set in this case as well, as $G-S$ stays connected.

Case 4: Two vertices of $S$ lie on layers 2 or 4 and one belongs to one of layers 1, 3 or 5.

This case is rather simple as the two vertices on the layer 2 or layer 4 are never adjacent. Thus, all the neighbors of $a, \; b$ and $c$ belong to layers 1, 3 & 5 and layer 2 & 4 regardless of whether the one vertex belongs to the layer-1, 3 or 5. All of the neighbors have degrees at least 2, which implies that $S$ is not a vertex cut set of $G$ while $G-S$ staying connected.

Case 5: Every vertex of $S$ lie on the different layer in $G$.

By following the same reasoning as in previous cases, we find that $G-S$ stays connected in this case as well.

Combining our discussion in Cases 1–5, we conclude that any set of three vertices in $G$ is never a vertex cut set of $G$. This shows that $\kappa(G)\geq 4$ and combining it with $\kappa(G)\leq 4$ finishes the proof to Claim 2.

Claim 3: $G$ is a Hamiltonian.

The following is the Hamiltonian cycle in $G$.

Claims 1, 2 & 3 show that $G$ is a family of Hamiltonian, 4-connected line graphs. By using Theorem 2.2, $G$ is Hamilton-connected.

Using Theorems 2.4 & 3.1, the following proposition computes the detour index of the line graph of $P_n$.

Corollary 3.2. Let $G = P_n$, where $n\geq5$. Then the detour index of $G$ is

Proof. The number of vertices in the line graph $G$ is $6n$. Replacing $6n$ with $n$ in Theorem 2.4 shows the proposition.

4.   Hamilton-connectedness and the detour index of $T_n$

For $n\geq 4$, the family of convex polytope $T_n$ is introduced in ^[3] which consists of 3, 4 & 5-sided faces.

The vertex set of $T_n$ consists of four layers of vertices i.e. $w_i$, $x_i$, $y_i$ and $z_i$. That is to say that $V(T_n) = \{w_i, x_i, y_i, z_i:1\leq i\leq n\}$. Accordingly, the edge set of $T_n$ is as follows:

The subscripts are to be considered modulo $n$. Figure 3 presents the $n$-dimensional convex polytope $T_n$ with proper labeling of vertices which will be used to show its Hamilton-connectedness.

Next, we show the main result of this section.

Theorem 4.1. The $n$-dimensional convex polytope $T_n$, with $n\geq4$, is Hamilton-connected.

Proof. We prove it by definition. This implies that we need to show the existence of Hamiltonian paths between any pair of vertices of $G$.

Let $P_H(u, v)$ denote a Hamiltonian path between vertices $u$ and $v$ of $T_n$. By following the labeling of vertices exhibited in Figure 3, we show the existence of Hamiltonian paths between vertices of $T_n$ in a number of cases.

Case 1: $u = z_1$ and $v = z_i$, $2 \leq i\leq n$

Subcase 1.1: $2 \leq i\leq n-1$

Subcase 1.2: $i = n$

Case 2: $u = z_1$ and $v = y_i$, $1 \leq i\leq n$

Subcase 2.1: $1 \leq i\leq n-1$

Subcase 2.2: $i = n$

Case 3: $u = z_1$ and $v = x_i$, $1 \leq i\leq n$

Subcase 3.1: $1 \leq i\leq n-1$

Subcase 3.2: $i = n$

Case 4: $u = z_1$ and $v = w_i$, $1 \leq i\leq n$

Subcase 4.1: $1 \leq i\leq n-1$

Subcase 4.2: $i = n$

Case 5: $u = y_1$ and $v = z_i$, $1 \leq i\leq n$

Subcase 5.1: $1 \leq i\leq n-1$

Subcase 5.2: $i = n$

Case 6: $u = y_1$ and $v = y_i$, $2 \leq i\leq n$

Subcase 6.1: $i = 2$

Subcase 6.2: $3 \leq i\leq n-1$

Subcase 6.3: $i = n$

Case 7: $u = y_1$ and $v = x_i$, $1 \leq i\leq n$

Subcase 7.1: $1 \leq i\leq n-1$

Subcase 7.2: $i = n$

Case 8: $u = y_1$ and $v = w_i$, $1 \leq i\leq n$

Subcase 8.1: $1 \leq i\leq n-1$

Subcase 8.2: $i = n$

Case 9: $u = x_1$ and $v = z_i$, $1 \leq i\leq n$

Subcase 9.1: $1 \leq i\leq n-1$

Subcase 9.2: $i = n$

Case 10: $u = x_1$ and $v = y_i$, $1 \leq i\leq n$

Subcase 10.1: $1 \leq i\leq n-1$

Subcase 10.2: $i = n$

Case 11: $u = x_1$ and $v = x_i$, $2 \leq i\leq n$

Subcase 11.1: $2 \leq i\leq n-1$

Subcase 11.2: $i = n$

Case 12: $u = x_1$ and $v = w_i$, $1 \leq i\leq n$

Subcase 12.1: $i = 1$

Subcase 12.2: $2 \leq i\leq n-1$

Subcase 12.3: $i = n$

Case 13: $u = w_1$ and $v = z_i$, $1 \leq i\leq n$

Subcase 13.1: $1 \leq i\leq n-1$

Subcase 13.2: $i = n$

Case 14: $u = w_1$ and $v = y_i$, $1 \leq i\leq n$

Subcase 14.1: $1 \leq i\leq n-1$

Subcase 14.2: $i = n$

Case 15: $u = w_1$ and $v = x_i$, $1 \leq i\leq n$

Subcase 15.1: $i = 1$

Subcase 15.2: $2 \leq i\leq n-1$

Subcase 15.3: $i = n$

Case 16: $u = w_1$ and $v = w_i$, $2 \leq i\leq n$

Subcase 16.1: $2 \leq i\leq n-1$

Subcase 16.2: $i = n$

This show the existence of Hamiltonian paths between any two vertices of $S_n$. This completes the proof.

Using Theorems 2.4 & 4.1, the following proposition calculates the detour index of $T_n$.

Corollary 4.2. Let $G = T_n$, where $n\geq3$. Then the detour index of $G$ is

Proof. The number of vertices in $G$ is $4n$. Replacing $4n$ with $n$ in Theorem 2.4 completes the proof.

5.   Hamilton-connectedness and the detour index of $A_n$

In this section, we show that the graph $A_n$ is Hamilton-connected. Next, we use the Hamilton-connectedness to find a formula for the detour index of the graph $A_n$. This family of convex polytopes were introduced by Imran et al. ^[14].

The vertex set of $A_n$, with $n\geq3$, is defined as $V(A_n) = \{u, v\}\bigcup \{w_i, x_i, y_i, z_i:1\leq i\leq n\}$. The edge set of $A_n$ is defined as

where the subscripts are performed modulo $n$. Figure 4 presents the $n$-dimensional convex polytope $A_n$ with proper labeling of vertices which will be used to show its Hamilton-connectedness.

The following the main result of this section.

Theorem 5.1. The graph $n$-dimensional convex polytope $A_n$, with $n\geq5$, is Hamilton-connected.

Proof. We prove this result by definition. For this we have to show that their exists Hamiltonian paths between any pair of vertices of $A_n$.

Let $P_H(x', y')$ denote a Hamiltonian path between vertices $x'$ and $y'$ in $A_n$. Let $A_n = U \cup Z \cup Y \cup X \cup W \cup V$ such that $U = \{u \}$, $Z = \{z_1, z_2, \ldots, z_n\}$, $Y = \{y_1, y_2...y_n\}$, $X = \{x_1, x_2, \ldots, x_n\}$, $W = \{w_1, w_2, \ldots, w_n\}$ and V = {v}. See Figure 4.

Case 1: $x' = u$ and $y' = z_i$, $1\leq i\leq n$

Subcase 1.1: $1\leq i\leq n-1$

Subcase 1.2: $i = n$

Case 2: $x' = u$ and $y' = y_i$, $1\leq i\leq n$

Subcase 2.1: $1\leq i\leq n-1$

Subcase 2.2: $i = n$

Case 3: $x' = u$ and $y' = x_i$, $1\leq i\leq n$

Subcase 3.1: $1\leq i\leq n-1$

Subcase 3.2: $i = n$

Case 4: $x' = u$ and $y' = w_i$, $1\leq i\leq n$

Subcase 4.1: $1\leq i\leq n-1$

Subcase 4.2: $i = n$

Case 5: $x' = u$ and $y' = v$

Case 6: $x' = v$ and $y' = u$

This case is similar to Case 5.

Case 7: $x' = v$ and $y' = z_i$, $1\leq i\leq n$

Subcase 7.1: $1\leq i\leq n-1$

Subcase 7.2: $i = n$

Case 8: $x' = v$ and $y' = y_i$, $1\leq i\leq n$

Subcase 8.1: $1\leq i\leq n-1$

Subcase 8.2: $i = n$

Case 9: $x' = v$ and $y' = x_i$, $1\leq i\leq n$

Subcase 9.1: $1\leq i\leq n-1$

Subcase 9.2: $i = n$

Case 10: $x' = v$ and $y' = w_i$, $1\leq i\leq n$

Subcase 10.1: $1\leq i\leq n-1$

Subcase 10.2: $i = n$

Case 11: $x' = z_1$ and $y' = u$

This case is similar to Case 1.

Case 12: $x' = z_1$ and $y' = z_i$, $2\leq i\leq n$

Subcase 12.1: $2\leq i\leq n-1$

Subcase 12.2: $i = n$

Case 13: $x' = z_1$ and $y' = y_i$, $1\leq i\leq n$

Subcase 13.1: $1\leq i\leq n-1$

Subcase 13.2: $i = n$

Case 14: $x' = z_1$ and $y' = x_i$, $1\leq i\leq n$

Subcase 14.1: $1\leq i\leq n-1$

Subcase 14.2: $i = n$

Case 15: $x' = z_1$ and $y' = w_i$, $1\leq i\leq n$

Subcase 15.1: $1\leq i\leq n-1$

Subcase 15.2: $i = n$

Case 16: $x' = z_1$ and $y' = v$

This case is similar to Case 7.

Case 17: $x' = y_1$ and $y' = u$

This case is similar to Case 2.

Case 18: $x' = y_1$ and $y' = z_i$, $1\leq i\leq n$

Subcase 18.1: $1\leq i\leq n-1$

Subcase 18.2: $i = n$

Case 19: $x' = y_1$ and $y' = y_i$, $2\leq i\leq n$

Subcase 19.1: $2\leq i\leq n-1$

Subcase 19.2: $i = n$

Case 20: $x' = y_1$ and $y' = x_i$, $1\leq i\leq n$

Subcase 20.1: $1\leq i\leq n-1$

Subcase 20.2: $i = n$

Case 21: $x' = y_1$ and $y' = w_i$, $1\leq i\leq n$

Subcase 21.1: $1\leq i\leq n-1$

Subcase 21.2: $i = n$

Case 22: $x' = y_1$ and $y' = v$

This case is similar to Case 8.

Case 23: $x' = x_1$ and $y' = u$

This case is similar to Case 3.

Case 24: $x' = x_1$ and $y' = z_i$, $1\leq i\leq n$

Subcase 24.1: $1\leq i\leq n-1$

Subcase 24.2: $i = n$

Case 25: $x' = x_1$ and $y' = y_i$, $1\leq i\leq n$

Subcase 25.1: $1\leq i\leq n-1$

Subcase 25.2: $i = n$

Case 26: $x' = x_1$ and $y' = x_i$, $2\leq i\leq n$

Subcase 26.1: $2\leq i\leq n-1$

Subcase 26.2: $i = n$

Case 27: $x' = x_1$ and $y' = w_i$, $1\leq i\leq n$

Subcase 27.1: $1\leq i\leq n-1$

Subcase 27.2: $i = n$

Case 28: $x' = x_1$ and $y' = v$

This case is similar to Case 9.

Case 29: $x' = w_1$ and $y' = u$

This case is similar to Case 4.

Case 30: $x' = w_1$ and $y' = z_i$, $1\leq i\leq n$

Subcase 30.1: $1\leq i\leq n-1$

Subcase 30.2: $i = n$

Case 31: $x' = w_1$ and $y' = y_i$, $1\leq i\leq n$

Subcase 31.1: $1\leq i\leq n-1$

Subcase 31.2: $i = n$

Case 32: $x' = w_1$ and $y' = x_i$, $1\leq i\leq n$

Subcase 32.1: $1\leq i\leq n-1$

Subcase 32.2: $i = n$

Case 33: $x' = w_1$ and $y' = w_i$, $2\leq i\leq n$

Subcase 33.1: $2\leq i\leq n-1$

Subcase 33.2: $i = n$

Existence of Hamiltonian path between any two vertices of the $A_n$ completes the proof.

Using Theorems 2.4 & 5.1, the following proposition computes the detour index of of $A_n$.

Corollary 5.2. Let $G = A_n$, where $n\geq4$. Then the detour index of $G$ is

Proof. The number of vertices in the graph $G$ is $4n+2$. Replacing $4n+2$ with $n$ in Theorem 2.4 shows the proposition.

6.   Hamilton-connectedness, Hamilton-laceability and the detour index of Platonic solids

In 3D geometry, Platonic solids are characterized as convex, regular polyhedron. In a polyhedron, two faces are congruent if they are identical in size and shape, whereas, two faces are said to be regular if its all sides and all angles are equal. A Platonic solid is constructed by regular and congruent polygonal faces such that the number of faces meeting at each vertex is same. There are only five polyhedrons which meet this criterion. They are named as the tetrahedron, the hexahedron/cube, the octahedron, the dodecahedron and the icosahedron. Platonic solids are named after the Athenian philosopher Plato, who gave the first insight into these three-dimensional solids.

A graph $G$ of a polyhedron $D$ is constructed by considering points (resp. lines) in $D$ as vertices (resp. edges) in $G$ such that the point-line incidency in $D$ is retained as vertex-edge incidency in $G$. Graphs of the five Platonic solids are depicted in Figures 5 and 6.

Based on the prime importance of Platonic solids in geometry, in this section we explore the hamiltoniancity related properties of the Platonic solids.

The following theorem shows that the tetrahedron graph is Hamilton-connected.

Theorem 6.1. The tetrahedron graph is Hamilton-connected.

Proof. To show Hamilton-connectedness for the tetrahedron graph, we ensure that there exists a Hamiltonian path between every pair of vertices. Following the labeling of vertices of the tetrahedron graph in Figure 5, Table 1 exhibits Hamiltonian paths between any two vertices of the tetrahedron. This show the result.

Using Theorems 2.4 & 6.1, the following proposition evaluates the detour index of the tetrahedron graph.

Proposition 6.2. Let $G$ be the tetrahedron graph, then $\omega(G) = 18$.

Note that the hexahedron/cube is bipartite, therefore, it can not be Hamilton-connected. However, the following theorem shows that the cube graph is, in fact, Hamilton-laceable.

Theorem 6.3. The hexahedron/cube graph is Hamilton-laceable.

Proof. Since the cube is bipartite. Let $\sigma = \{U, V\}$ be the bipartition of the cube. Then following the vertex labeling of the cube from Figure 5, we find that $U = \{u_i: 1\leq i\leq4\}$ and $V = \{v_i: 1\leq i\leq4\}$. We need show Hamiltonian paths between vertices of $U$ and $V$. Table 2 presents all the Hamiltonian paths between vertices of two different partite sets i.e., $U$ and $V$, for the cube. This completes the proof.

Next we study Hamiltoniancity in the dodecahedron. Interestingly, the dodecahedron is neither bipartite nor Hamilton-connected.

Theorem 6.4. The dodecahedron graph is neither Hamilton-connected nor Hamilton-laceable.

Proof. There are pentagonal faces in the dodecahedron which make it a non-bipartite graph. Thus, by definition, it is not Hamilton-laceable.

Following the labeling of vertices in Figure 5, we see that there exists no Hamiltonian path between $v_2$ and $v_{19}$. Thus it is not Hamilton-connected.

The following theorem shows that the octahedron graph is Hamilton-connected.

Theorem 6.5. The octahedron graph is Hamilton-connected.

Proof. To show that the octahedron graph is Hamilton-connected, we construct Hamiltonian paths between each pair of vertices of the octahedron. Let $x$ and $y$ denote arbitrary vertices of the octahedron. Given the vertex labeling of the octahedron in Figure 6, the following two cases comprise all Hamiltonian paths between $x$ and $y$.

Case 1: $x = v_1$, $y = v_i, \; \text{where} \; i = 2, 3$

Case 2: $x = v_1$, $y = u_i, \; \text{where} \; i = 1, 2, 3$

Subcase 2.1: $i = 1, 3$

Subcase 2.2: $i = 2$

This completes the proof.

Using Theorems 2.4 & 6.5, the following proposition computes the detour index of the octahedron graph.

Proposition 6.6. Let $G$ be the octahedron graph, then $\omega(G) = 75$.

Finally, the following theorem shows that the icosahedron graph is also Hamilton-connected.

Theorem 6.7. The icosahedron graph is Hamilton-connected.

Proof. To show that the icosahedron graph is Hamilton-connected, we construct Hamiltonian paths between each pair of vertices of the icosahedron. Let $x$ and $y$ denote arbitrary vertices of the icosahedron. Given the vertex labeling of the icosahedron in Figure 6, the following two cases comprise all Hamiltonian paths between $x$ and $y$.

Case 1: $x = v_1$, $y = v_i, \; \text{where} \; i = 2, 3$

Case 2: $x = v_1$, $y = u_i, \; \text{where} \; i = 1, 2, 3, ..., 6$

Subcase 2.1: $i = 1$

Subcase 2.2: $i = 2, 3, 4$

Subcase 2.3: $i = 5, 6$

Case 3: $x = v_1$, $y = w_i, \; \text{where} \; i = 1, 2, 3$

Subcase 3.1: $i = 1$

Subcase 3.2: $i = 2, 3$

This completes the proof.

Using Theorems 2.4 & 6.7, the following proposition calculates the detour index of the icosahedron graph.

Proposition 6.8. Let $G$ be the icosahedron graph, then $\omega(G) = 726$.

7.   Conclusions and future work

Computing the detour index of a graph is NP-complete and checking if a graph is Hamilton-connected is also NP-complete. Thus, it is natural to study these problems for special families of graphs. This paper consider certain infinite families of planar geometric graphs. We construct three infinite families of Hamilton-connected convex polytope networks. More importantly, we compute exact analytical expressions for the detour index of the families of Hamilton-connected convex polytope networks.

In view of the work of the work by Alspach & Liu ^[1], we propose the following conjectures:

Conjecture 7.1. (i) The generalized Petersen graph $GP(n, 4)\; n\geq9$ is non-bipartite Hamilton-connected.

(ii) The generalized Petersen graph $GP(n, 5)\; n\geq11$ is non-bipartite Hamilton-connected if $n\mid2$ and bipartite Hamilton-laceable if $n\nmid2$.

Acknowledgements

Sakander Hayat is grateful to Dr. Muhammad Imran for providing the registration information of Mayura draw. The authors are grateful to the handling editor and the anonymous reviewer for a careful reading of this paper and for all their comments and remarks, which lead to a number of improvements of the paper.

S. Hayat is supported by the Higher Education Commission, Pakistan under grant number 20-11682/NRPU/RGM/R & D/HEC/2020.

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.