# Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index

Authors: Sakander Hayat; Asad Khan; Suliman Khan; Jia-Bao Liu
Journal: Complexity
 (2021)

---

## Abstract

A connected graph is called Hamilton-connected if there exists a Hamiltonian path between any pair of its vertices. Determining whether a graph is Hamilton-connected is an NP-complete problem. Hamiltonian and Hamilton-connected graphs have diverse applications in computer science and electrical engineering. The detour index of a graph is defined to be the sum of lengths of detours between all the unordered pairs of vertices. The detour index has diverse applications in chemistry. Computing the detour index for a graph is also an NP-complete problem. In this paper, we study the Hamilton-connectivity of convex polytopes. We construct three infinite families of convex polytopes and show that they are Hamilton-connected. An infinite family of non-Hamilton-connected convex polytopes is also constructed, which, in turn, shows that not all convex polytopes are Hamilton-connected. By using Hamilton connectivity of these families of graphs, we compute exact analytical formulas of their detour index.


---

## Body

## 1. Introduction and Preliminaries

All graphs in this paper are simple, loopless, finite, and connected.A cycle in a graphG is called Hamiltonian if it travels all the vertices of G. Moreover, a path in G is called Hamiltonian path if it traverses all the vertices of G. Not every graph contains a Hamiltonian cycle. For instance, any tree is an acyclic graph, so it cannot 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 nontrivial 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 ofG is called Hamilton connected. They were introduced by Ore [1] in 1963. Frucht [2] studied a canonical representation of trivalent Hamiltonian graphs. A bipartite can never be a Hamilton-connected, since there cannot exist a Hamiltonian path between vertices of the same partite set. In that case, a bipartite graph is called Hamilton-laceable if there exist Hamiltonian paths between vertices of different partite sets. There is an extensive literature available on Hamiltoniancity and Hamilton-connectivity of graphs, see, for instance, [3–7].Chartrand et al. [8] showed that the square of a block graph is Hamilton-connected. Thomasson [9] studied Hamilton-connected tournaments in graphs. Chang et al. [10] studied panconnectivity, fault-tolerant Hamiltonicity, and Hamiltonian-connectivity in alternating group graphs by considering them as interconnection networks. Kewen et al. [11] derived a sufficient condition for a graph to be Hamilton-connected. Zhou and Wang [12] 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. [13] calculated the Wiener and Harary indices of Hamilton-connected graphs with large diameter. Wei et al. [14] derived some spectral analogues of Erdös’ theorems for Hamilton-connected graphs. Hung et al. [15] studied Hamilton-connectivity of alphabet grid graphs. Zhou et al. [16] 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. [17] studied Hamilton-connectivity in Teoplitz graphs.By preserving the vertex-edge incidence relation in convex polytopes, their graphs are constructed. Bača [18–20] was the first researcher to consider these families of geometric graphs. In [20] (resp. [19]), Bača studied the problem of magic (resp. graceful and antigraceful) labeling of convex polytopes, whereas, in [18], the problem of face antimagic labeling of convex polytopes was studied. Miller et al. [21] studied the vertex-magic total labeling of convex polytopes. Imran et al. [22–24] computed the minimum metric dimension of various infinite families of convex polytopes. In particular, they showed that these infinite families of convex polytopes have constant metric dimension. Malik et al. [25] also constructed two infinite families of convex polytopes having constant metric dimension. Other closely related infinite families of graphs with constant metric dimension are studied in [26]. Kratica et al. [27] studied the strong metric dimension of certain infinite families of convex polytopes by constructing their doubly resolving sets. The fault-tolerant metric dimension (resp. mixed metric dimension) of convex polytopes was studied by Raza et al. [28] (resp. Raza et al. [29]). Metric dimension of other related families of graphs such as Cayley graph is studied by Vetrik and Abas [30, 31]. The binary locating-dominating number of convex polytopes is studied by Simić et al. [32] and Raza et al. [33]. The open-locating-dominating number of certain convex polytopes has recently been studied by Savic et al. [34]. Liu et al. [35–39] studied application of various graph parameters in electrical networks and related systems.For a graphG, let ℓx,y be the length of a longest path (i.e., detour) between vertices x and y of G. The detour index [40] is defined to be the sum of lengths of all detours between unordered pairs of vertices in G. The detour index of a graph G is usually denoted by ωG:(1)ωG=∑x,y⊂VGℓx,y.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 [41]. Besides giving further applications of the detour index, Trinajstić et al. [42] conducted a comparative analysis with the Wiener index in terms of applicability in correlating structure boiling point of organic compounds. Moreover, its further applications in predicting the normal boiling points of cyclic and acyclic alkanes were studied by Rücker and Rücker [43].An algorithm for tracing the detour between two vertices in a graph was proposed by Lukovits and Razinger [44]. 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 [43] and Trinajstić et al. [45] proposed certain computer methods to trace out detours and thus calculation of the detour index of graphs. It has already been shown in [46] that the problem of finding the detour index of a given graph is computationally NP-complete. Trinajstić et al. [45] 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.Mahmiani et al. [47] proposed the edge versions of the detour index and studied their mathematical properties. Zhou and Cai [48] proved some upper and lower bounds on the detour index of graphs. Qi and Zhou [49] studied minimum uncyclic graphs with respect to the detour index. Du [50] studied the minimum detour index of bicyclic graphs. Fang et al. [51] characterized the minimum detour index of some families of tricyclic graphs. Karbasioun et al. [52] studied the applications of the detour index in infinite families of nanostar dendrimers. Wu and Deng [53] computed the detour index for a chain of C20 fullerenes. Kaladevi [54] studied spectral properties of the detour index in relation with the Laplacian energy of graphs. Recently, Abdullah and Omar [55] introduced the restricted edge version of the detour index and studied it for some families of graphs.We end this section with an important and well-known result bounding the detour index in terms of graph parameters.Theorem 1 (see [56]).
LetG be a connected graph with n≥3 vertices. Then,(2)n−12≤ωG≤nn−122,with left equality if and only if G≅Sn and with right equality if and only if G is Hamilton-connected.In this paper, we study the Hamilton connectivity of certain infinite families of convex polytopes. More precisely, we construct three infinite families of Hamilton-connected convex polytopes. Moreover, we construct an infinite family non-Hamilton-connected convex polytope. By using Hamilton-connectivity of these families of graphs, we compute exact formulas of their detour index.


## 2. Hamilton Connectivity and the Detour Index ofRn

In this section, we show that then-dimensional infinite family of convex polytopes Rn is Hamilton-connected. Afterwards, we use its Hamiltonconnectivity to find analytical exact expression of the detour index of the graph Rn.Forn≥5, the graph of convex polytope Rn is defined in [20]. It has the vertex set(3)VRn=xj;yj;zj:1≤j≤n,and edge set(4)ERn=xj,xj+1;xj,yj;xj+1,yj;yj,yj+1;yj,zj;zj,zj+1:1≤j≤n.By convention, we suppose thatxn+1=xn, yn+1=yn, and zn+1=zn. See Figure 1 to view the n-dimensional convex polytope Rn.Figure 1
Then-dimensional convex polytope Rn.For a positive integerν∈ℤ+, we write ν|2 (resp. ν∤2) if ν is even (resp. odd).Theorem 2.
Then-dimensional convex polytope Rn, with n≥4, is Hamilton-connected.Proof.
We prove this result by definition. For this, we have to show that there exists a Hamiltonian path between any pair of vertices ofRn.
LetPHu,v be a Hamiltonian path between vertices u and v in Rn. Let VRn=Z∪Y∪X such that Z=z1,z2,…,zn, Y=y1,y2…yn, and X=x1,x2,…,xn, see, Figure 1.Case 1:u=z1 and v=zi, 2≤i≤n.Case 1.1:2≤i≤n−1:(5)PHu,v:u=z1∼zn−j:0≤j≤n−i−1∼yi−j+1:0≤j≤i−2∼xj:3≤j≤i+1∼xjyj:i+2≤j≤n∼x1y1x2y2∼zj:2≤j≤i=v.Case 1.2:i=n:(6)PHu,v:u=z1y1∼xj:1≤j≤n∼yn−j:0≤j≤n−2∼zj:2≤j≤n=v.Case 2:u=z1 and v=yi, 1≤i≤n.Case 2.1:1≤i≤n−1:(7)PHu,v:u=z1∼zj:2≤j≤n∼yn−j:0≤j≤n−i−1∼xj:i+1≤j≤n∼xjyj:1≤j≤i=v.Case 2.2:i=n:(8)PHu,v:u=z1y1∼xj:1≤j≤n∼yn−j:1≤j≤n−2∼zj:2≤j≤n∼yn=v.Case 3:u=z1 and v=xi, 1≤i≤n.Case 3.1:i=1:(9)PHu,v:u=z1∼zj:2≤j≤n∼yn−j:0≤j≤n−1∼xj:2≤j≤n∼x1=v.Case 3.2:2≤i≤n:(10)PHu,v:u=z1∼zj:2≤j≤n∼yn−j:0≤j≤n−i∼yi−jxi−j:1≤j≤i−1∼xn−j:0≤j≤n−i=v.Case 4:u=y1 and v=zi, 1≤i≤n.Case 4.1:i=1:(11)PHu,v:u=y1∼xj:1≤j≤n∼yn−j:0≤j≤n−2∼zj:2≤j≤n∼z1=v.Case 4.2:2≤i≤n−1:(12)PHu,v:u=y1x1∼xjyj:2≤j≤i∼xj:i+1≤j≤n∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤n∼zj:1≤j≤i=v.Case 4.3:i=n:(13)PHu,v:u=y1∼zj:1≤j≤n−1∼yn−j:1≤j≤n−2∼xj:2≤j≤n∼x1ynzn=v.Case 5:u=y1 and v=yi, 2≤i≤n.Case 5.1:i=2:(14)PHu,v:u=y1∼xj:1≤j≤n∼yn−j:0≤j≤n−3∼zj:3≤j≤n∼z1z2y2=v.Case 5.2:3≤i≤n−1:(15)PHu,v:u=y1x1∼xjyj:2≤j≤i−1∼xj:i≤j≤n∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤n∼zj:1≤j≤i=v.Case 5.3:i=n:(16)PHu,v:u=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n−1∼xn−j:0≤j≤n−1∼yn=v.Case 6:u=y1 and v=xi, 1≤i≤n.Case 6.1:i=1,2:(17)PHu,v:u=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:i+1≤j≤n∼xj:1≤j≤i=v.Case 6.2:3≤i≤n−1:(18)PHu,v:u=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−i∼xj:i+1≤j≤n∼x1∼xjyj:2≤j≤i−1∼xi=v.Case 6.3:i=n:(19)PHu,v:u=y1x1ynzn∼zj:1≤j≤n−1∼yn−j:1≤j≤n−2∼xj:2≤j≤n=v.Case 7:u=x1 and v=zi, 1≤i≤n.Case 7.1:i=1:(20)PHu,v:u=x1∼xn−j:0≤j≤n−2∼yj:1≤j≤n∼zn−j:0≤j≤n−2∼z1=v.Case 7.2:i=2:(21)PHu,v:u=x1∼xj:2≤j≤n∼yn−j:0≤j≤n−1∼z1∼zn−j:0≤j≤n−3∼z2=v.Case 7.3:3≤i≤n:(22)PHu,v:u=xjyj:1≤j≤i−2∼xj:i−1≤j≤n∼yn−j:0≤j≤n−i+1∼zi−j:1≤j≤i−1∼zn−j:0≤j≤n−i=v.Case 8:u=x1 and v=yi, 1≤i≤n.Case 8.1:i=1:(23)PHu,v:u=x1∼xj:2≤j≤n∼yn−j:0≤j≤n−2∼zj:2≤j≤n∼z1y1=v.Case 8.2:2≤i≤n−1:(24)PHu,v:u=xjyj:1≤j≤i−1∼xj:i≤j≤n∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤n∼zj:1≤j≤i∼yi=v.Case 8.3:i=n:(25)PHu,v:u=x1∼xj:2≤j≤n∼yn−j:1≤j≤n−1∼zj:1≤j≤n∼zn=v.Case 9:u=x1 and v=xi, 2≤i≤n.Case 9.1:2≤i≤n−1:(26)PHu,v:u=x1∼xn−j:0≤j≤n−i−1∼yj:i≤j≤n∼zn−j:0≤j≤n−1∼yj−1xj:2≤j≤i=v.Case 9.2:i=n:(27)PHu,v:u=x1∼xj:2≤j≤n−1∼yn−j:1≤j≤n−1∼zj:1≤j≤n∼ynxn=v.
Existence of Hamiltonian path between any two vertices of then-dimensional convex polytope Rn completes the proof.
Using Theorems1 and 2, the following proposition computes the detour index of of Rn.Proposition 1.
LetG=Rn, where n≥4. Then, the detour index of G is(28)ωG=3n3n−122.Proof.
The number of vertices in the graphG is 3n. Replacing 3n with n in Theorem 1 shows the proposition.


## 3. Hamilton Connectivity and the Detour Index ofSn

In this section, we show that then-dimensional infinite family of convex polytopes Sn is Hamilton-connected. Then, we use its Hamilton connectivity to find analytical exact expression of the detour index of the graph Sn.The graph of convex polytopeSn (Figure 2) consists of 2n 3-sided faces, 2n 4-sided faces, and a pair of n-sided faces [57]. We have(29)VSn=wj;xj;yj;zj:1≤j≤n,ESn=wjwj+1;xjxj+1;yjyj+1;zjzj+1:1≤j≤n∪wj+1xj;wjxj;xjyj;yjzj:1≤j≤n.Figure 2
Then-dimensional convex polytope Sn.See Figure2 to view the n-dimensional convex polytope Sn.Next, we show the main result of this section.Theorem 3.
Then-dimensional convex polytope Sn, with n≥4, 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 ofG.
LetPHu,v be a Hamiltonian path between vertices u and v in Sn. By following the labeling of vertices exhibited in Figure 2, we show the existence of Hamiltonian paths between vertices of Sn in a number of cases.Case 1:u=z1 and v=zi, 2≤i≤n.Case 1.1:i|2:(30)PHu,v:u=z1y1x1w1∼wj−nxj−nyj−nzj−nzj−n+1yj−n+1xj−n+1wj−n+1:n+2≤j≤n+i2∼wj:i≤j≤n∼xn−j:0≤j≤n−i∼yj:i≤j≤n∼zn−j:0≤j≤n−i=v.Case 1.2: i∤2:(31)PHu,v:u=z1∼zj:2≤j≤i−1∼yj:i−1≤j≤n−1∼xn−j:1≤j≤n−i+1∼wj:i−1≤j≤n∼xn∼wj:1≤j≤i−2∼xi−jyi−jyi−j−1xi−j−1:2≤j≤i−12∼x1y1yn∼zn−j:0≤j≤n−i=v.Case 2:uz1andvyi,1≤i≤n:Case 2.1:1≤i≤n−1:(32)PHu,v:u=z1∼zj:2≤j≤n∼yn−j:0≤j≤n−i−1∼xj:i+1≤j≤n∼w1∼wn−j:0≤j≤n−i−1∼xi−jwi−j:0≤j≤i−2∼x1∼yj:1≤j≤i=v.Case 2.2: i=n:(33)PHu,v:u=z1y1x1xnw1∼wn−j:0≤j≤n−2∼xj:2≤j≤n−1∼yn−j:1≤j≤n−2∼zj:2≤j≤n∼yn=v.Case 3:u=z1 and v=xi, 1≤i≤n.Case 3.1:i=1:(34)PHu,v:u=z1∼zn−j:0≤j≤n−2∼y1∼yn−j:0≤j≤n−3∼xj:3≤j≤n∼w1∼wn−j:0≤j≤n−2∼x2x1=v.Case 3.2: 2≤i≤n−1:(35)PHu,v:u=z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼y1x1∼xn−j:0≤j≤n−i−1∼wj:i+1≤j≤n∼w1∼wjxj:2≤j≤i=v.Case 3.3: i=n:(36)PHu,v:u=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n−1∼wn−j:0≤j≤n−1∼xn=v.Case 4:u=z1 and v=wi, 1≤i≤n.Case 4.1:i=1:(37)PHu,v:u=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n∼wn−j:0≤j≤n−1=v.Case 4.2: 2≤i≤n−1:(38)PHu,v:u=zj:1≤j≤n∼yn∼yj:1≤j≤n−1∼xn−j:1≤j≤n−i∼wj:i+1≤j≤n∼w1xn∼xj−1wj:2≤j≤i=v.Case 4.3: i=n:(39)PHu,v:u=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n∼wj:1≤j≤n=v.Case 5:u=y1 and v=zi, 1≤i≤n.Case 5.1:i=1:(40)PHu,v:u=yj:1≤j≤n−1∼xn−j:1≤j≤n−1∼wj:1≤j≤n∼xnyn∼zn−j:0≤j≤n−1=v.Case 5.2: 2≤i≤n−1:(41)PHu,v:u=yj:1≤j≤i∼xi−jwi−j:0≤j≤i−1∼wn−j:0≤j≤n−i−1∼xj:i+1≤j≤n∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤nzj:1≤j≤i=v.Case 5.3: i=n:(42)PHu,v:u=y1∼zj:1≤j≤n−1∼yn−j:1≤j≤n−2∼xj:2≤j≤n−1∼wn−j:0≤j≤n−1∼x1xnynzn=v.Case 6:u=y1 and v=yi, 2≤i≤n.Case 6.1:2≤i≤n−1:(43)PHu,v:u=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−i−1∼xi−j+1:0≤j≤i−2∼wj:3≤j≤i+1∼wjxj:i+2≤j≤n∼w1x1w2x2∼yj:2≤j≤i=v.Case 6.2: i=n:(44)PHu,v:u=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n−1∼xn−j:1≤j≤n−1∼wj:1≤j≤n∼xnyn=v.Case 7:u=y1 and v=xi, 1≤i≤n.Case 7.1:1≤i≤n−1:(45)PHu,v:u=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−i−1∼wj:i+1≤j≤n∼wjxj:1≤j≤i=v.Case 7.2: i=n:(46)PHu,v:u=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n−1∼wn−j:0≤j≤n−1∼x1xn=v.Case 8:u=y1 and v=wi, 1≤i≤n.Case 8.1:i=1:(47)PHu,v:u=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−1∼wj:2≤j≤n∼w1=v.Case 8.2: 2≤i≤n:(48)PHu,v:u=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−i∼xi−jwi−j:1≤j≤i−1∼wn−j:0≤j≤n−i=v.Case 9:u=x1 and v=zi, 1≤i≤n.Case 9.1:i=1:(49)PHu,v:u=x1∼yj:1≤j≤n−1∼xn−j:1≤j≤n−2∼wj:2≤j≤n∼x1xnyn∼zn−j:0≤j≤n−1=v.Case 9.2: 2≤i≤n−1:(50)PHu,v:u=x1y1z1∼zn−j:0≤j≤n−i−1∼yj:i+1≤j≤n∼xn−j:0≤j≤n−i−1∼wj:i+1≤j≤n∼w1∼wjxj:2≤j≤i∼yi−j:0≤j≤i−2∼zj:2≤j≤i=v.Case 9.3: i=n:(51)PHu,v:u=x1w1∼wn−j:0≤j≤n−2∼xj:2≤j≤n∼yn−j:0≤j≤n−1∼zj:1≤j≤n=v.Case 10:u=x1 and v=yi, 1≤i≤n.Case 10.1:i=1:(52)PHu,v:u=x1∼wj:1≤j≤n∼xn−j:0≤j≤n−2∼yj:2≤j≤n∼zn−j:0≤j≤n−1∼y1=v.Case 10.2: 2≤i≤n−1:(53)PHu,v:u=x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−i−1∼xjwj:i+1≤j≤n∼wj:1≤j≤i∼xi−j:0≤j≤i−2∼yj:2≤j≤i=v.Case 10.3: i=n:(54)PHu,v:u=x1y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n−1∼xn−j:1≤j≤n−2∼wj:2≤j≤n∼w1xnyn=v.Case 11:u=x1 and v=xi, 2≤i≤n.Case 11.1:2≤i≤n−1:(55)PHu,v:u=x1y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−i−1∼wj:i+1≤j≤n∼w1∼wjxj:2≤j≤i=v.Case 11.2: i=n:(56)PHu,v:u=x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n−1∼wn−j:0≤j≤n−1∼xn=v.Case 12:u=x1 and v=wi, 1≤i≤n.Case 12.1:i=1:(57)PHu,v:u=x1y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−2∼wj:2≤j≤n∼w1=v.Case 12.2: 2≤i≤n−1:(58)PHu,v:u=x1y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−i∼wj:i+1≤j≤n∼w1∼wjxj:2≤j≤i−1∼wi=v.Case 12.3: i=n:(59)PHu,v:u=xj:1≤j≤n−1∼yn−j:0≤j≤n−1∼zj:1≤j≤n∼ynxn∼wj:1≤j≤n=v.Case 13:u=w1 and v=zi, 1≤i≤n.Case 13.1:i=1:(60)PHu,v:u=wj:1≤j≤n∼xn−j:0≤j≤n−1∼yj:1≤j≤n∼zn−j:0≤j≤n−1=v.Case 13.2: 2≤i≤n:(61)PHu,v:u=wjxj:1≤j≤i−1∼wj:i≤j≤n∼xn−j:0≤j≤n−i∼yj:i≤j≤n∼yj:1≤j≤i−1∼zi−j:1≤j≤i−1∼zn−j:0≤j≤n−i=v.Case 14:u=w1 and v=yi, 1≤i≤n.Case 14.1:i=1:(62)PHu,v:u=w1∼wn−j:0≤j≤n−2∼xj:1≤j≤n∼yn−j:0≤j≤n−2∼zj:2≤j≤n∼z1y1=v.Case 14.2: 2≤i≤n−1:(63)PHu,v:u=wjxj:1≤j≤i∼wj:i+1≤j≤n∼xn−j:0≤j≤n−i−1∼yj:1≤j≤i−1∼zi−j:1≤j≤i−1∼zn−j:0≤j≤n−i∼yi=v.Case 14.3: i=n:(64)PHu,v:u=wj:1≤j≤n∼xn−j:0≤j≤n−1∼yj:1≤j≤n−1∼zn−j:1≤j≤n−1∼znyn=v.Case 15:u=w1 and v=xi, 1≤i≤n.Case 15.1:i=1:(65)PHu,v:u=wj:1≤j≤n∼xn−j:0≤j≤n−2∼yj:2≤j≤n∼zn−j:0≤j≤n−1∼y1x1=v.Case 15.2: 2≤i≤n−1:(66)PHu,v:u=wjxj:1≤j≤i−1∼wj:i≤j≤n∼xn−j:0≤j≤n−i−1∼yj:i+1≤j≤n∼yj:1≤j≤i−1∼zi−j:1≤j≤i−1zn−j:0≤j≤n−i∼yixi=v.Case 15.3: i=n:(67)PHu,v:u=w1∼wn−j:0≤j≤n−2∼xj:1≤j≤n−1∼yn−j:1≤j≤n−1∼zj:1≤j≤n∼ynxn=v.Case 16:u=w1 and v=wi, 2≤i≤n.Case 16.1:2≤i≤n−1:(68)PHu,v:u=w1∼wn−j:0≤j≤n−i−1∼xj:i≤j≤n∼yn−j:0≤j≤n−2∼zj:2≤j≤n∼z1y1x1∼wjxj:2≤j≤i−1∼wi=v.Case 16.2: i=n:(69)PHu,v:u=wj:1≤j≤n−1∼xn−j:1≤j≤n−1∼yj:1≤j≤n−1∼zn−j:1≤j≤n−1∼znynxnwn=v.
Existence of Hamiltonian paths between any two vertices of then-dimensional convex polytope Sn completes the proof.
Using Theorems1 and 3, the following proposition computes the detour index of Sn.Proposition 2.
LetG=Sn, where n≥3. Then, the detour index of G is(70)ωG=4n4n−122.Proof.
The number of vertices in graphG is 4n. Replacing 4n with n in Theorem 1 completes the proof.


## 4. Hamilton Connectivity and the Detour Index ofKn

This section shows that then-dimensional convex polytope Kn is Hamilton-connected. Its Hamilton connectivity is then used to calculate exact analytical formula of the detour index of Kn.Malik et al. [25] introduced the family of n-dimensional convex polytope Kn. We have(71)VKn=vi;wj;xj;yj;zj:1≤j≤n,EKn=vjvj+1;wjwj+1;xjxj+1;yjyj+1;zjzj+1:1≤j≤n∪vjyj;vjwj+1;wjxj;xjyj;xjyj+1;yjzj:1≤j≤n.See Figure3 to view the n-dimensional convex polytope Kn.Figure 3
The graph ofn-dimensional convex polytope Kn.Theorem 4.
The graphn-dimensional convex polytope Kn, with n≥5, is Hamilton-connected.Proof.
We prove this result by definition. For this, we have to show that there exists a Hamiltonian path between any pair of vertices ofKn.
LetPHu′,v′ be a Hamiltonian path between vertices u′ and v′ in Kn. Let VRn=Z∪Y∪X∪V such that Z=z1,z2,…,zn, Y=y1,y2…yn, X=x1,x2,…,xn, and V=v1,v2,…,vn. We divide the construction of Hamiltonian paths in Kn into a number of cases as follows.Case 1:u′=z1 and v′=zi, 2≤i≤n.Case 1.1:2≤i≤n−1:(72)PHu′,v′:u′=z1∼zn−j:0≤j≤n−i−1∼yj:i+1≤j≤n∼xn−j:0≤j≤n−i∼yi−jxi−j−1:0≤j≤i−3∼wj:2≤j≤n∼vn−j:0≤j≤n−1∼w1x1y1y2∼zj:2≤j≤i=v′.Case 1.2: i=n:(73)PHu′,v′:u′=zj:1≤j≤n−1∼yn−j:1≤j≤n−1∼xj:1≤j≤n−1∼wn−j:1≤j≤n−1∼vj:1≤j≤n∼wnxnynzn=v′.Case 2:u′=z1 and v′=yi, 1≤i≤n.Case 2.1:1≤i≤n−1:(74)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−i−1∼xj:i+1≤j≤n∼wn−j:0≤j≤n−i−1∼vj:i+1≤j≤n∼vjwj:1≤j≤i∼xi−j:0≤j≤i−1∼yj:1≤j≤i=v′.Case 2.2: i=n:(75)PHu′,v′:u′=z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n−1∼xn−j:1≤j≤n−2∼wj:2≤j≤n∼vn−j:0≤j≤n−1∼w1x1y1xnyn=v′.Case 3:u′=z1 and v′=xi, 1≤i≤n.Case 3.1:1≤i≤n−1:(76)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xn−j:0≤j≤n−i−1∼wj:i+1≤j≤n∼v1∼vn−j:0≤j≤n−i−1∼wi−jvi−j:0≤j≤i−2∼w1∼xj:1≤j≤i=v′.Case 3.2: i=n:(77)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n−1∼wn−j:1≤j≤n−1∼vj:1≤j≤n∼wnxn=v′.Case 4:u′=z1 and v′=wi, 1≤i≤n.Case 4.1:1≤i≤n−1:(78)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n∼wn−j:0≤j≤n−i−1∼vj:i+1≤j≤n∼vjwj:1≤j≤i=v′.Case 4.2: i=n:(79)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n−2∼wn−j:2≤j≤n−1∼vj:1≤j≤n∼wn−1xn−1xnwn=v′.Case 5:u′=z1 and v′=vi, 1≤i≤n.Case 5.1:1≤i≤n−1:(80)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n∼wn−j:0≤j≤n−i∼vj:i+1≤j≤n∼vjwj:1≤j≤i−1∼vi=v′.Case 5.2: i=n:(81)PHu′,v′:u′=zj:1≤j≤n∼yn−j:0≤j≤n−1∼xj:1≤j≤n∼wn−j:0≤j≤n−1∼vj:1≤j≤n=v′.Case 6:u′=y1 and v′=zi, 1≤i≤n:Case 6.1:1≤i≤n−1:(82)PHu′,v′:u′=yjxj:1≤j≤i∼xj:i+1≤j≤n−1∼wn−j:1≤j≤n−1∼vj:1≤j≤n∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤n∼zj:1≤j≤i=v′.Case 6.2: i=n:(83)PHu′,v′:u′=y1∼zj:1≤j≤n−1∼yn−j:1≤j≤n−2∼xj:1≤j≤n−1∼wn−j:1≤j≤n−1∼vj:1≤j≤n∼wnxnynzn=v′.Case 7:u′=y1 and v′=yi, 2≤i≤nCase 7.1:2≤i≤n−1:(84)PHu′,v′:u′=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−i−1∼xj:i≤j≤n∼wn−j:0≤j≤n−2∼vj:2≤j≤n∼v1w1∼xj−1yj:2≤j≤i=v′.Case 7.2: i=n:(85)PHu′,v′:u′=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n−1∼xn−j:1≤j≤n−1∼wj:1≤j≤n−1∼vn−j:0≤j≤n−1∼wnxnyn=v′.Case 8:u′=y1 and v′=xi, 1≤i≤n.Case 8.1:1≤i≤n−1:(86)PHu′,v′:u′=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−i−1∼wi+1vi+1∼vjwj:i+2≤j≤n∼vj:1≤j≤i∼wi−j:0≤j≤i−1xj:1≤j≤i=v′.Case 8.2: i=n:(87)PHu′,v′:u′=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:1≤j≤n−1∼wn−j:1≤j≤n−1∼vj:1≤j≤n∼wnxn=v′.Case 9:u′=y1 and v′=wi, 1≤i≤n.Case 9.1:1≤i≤n−1:(88)PHu′,v′:u′=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:1≤j≤n∼wn−j:0≤j≤n−i−1∼vj:i+1≤j≤n∼vjwj:1≤j≤i=v′.Case 9.2: i=n:(89)PHu′,v′:u′=y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−1∼wj:1≤j≤n−1∼vn−j:0≤j≤n−1∼wn=v′.Case 10:u′=y1 and v′=vi, 1≤i≤n.Case 10.1:1≤i≤n−1:(90)PHu′,v′:u′=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:1≤j≤n∼wn−j:0≤j≤n−i∼vj:i+1≤j≤n∼vjwj:1≤j≤i−1∼vi=v′.Case 10.2: i=n:(91)PHu′,v′:u′=y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:1≤j≤n∼wn−j:0≤j≤n−1∼vj:1≤j≤n=v′.Case 11:u′=x1 and v′=zi, 1≤i≤n.Case 11.1:1≤i≤n−1:(92)PHu′,v′:u′=x1∼yjxj:2≤j≤i∼wi−j:0≤j≤i−1∼wn−j:0≤j≤n−i−2∼vj:i+2≤j≤n∼vj:1≤j≤i+1∼wi+1∼xj:i+1≤j≤n∼y1∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤n∼zj:1≤j≤i=v′.Case 11.2: i=n:(93)PHu′,v′:u′=x1w1∼vj:1≤j≤n∼wn−j:0≤j≤n−2∼xj:2≤j≤n∼yn−j:0≤j≤n−1∼zj:1≤j≤n=v′.Case 12:u′=x1 and v′=yi, 1≤i≤n.Case 12.1:i=1:(94)PHu′,v′:u′=x1w1v1∼vn−j:0≤j≤n−2∼wj:2≤j≤n∼xn−j:0≤j≤n−2∼yj:2≤j≤n∼zn−j:0≤j≤n−1∼y1=v′.Case 12.2: 2≤i≤n−1:(95)PHu′,v′:u′=x1w1v1∼vn−j:0≤j≤n−2∼wj:2≤j≤n∼xn−j:0≤j≤n−i∼yj:i+1≤j≤n∼zn−j:0≤j≤n−1∼y1∼yjxj:2≤j≤i−1∼yi=v′.Case 12.3: i=n:(96)PHu′,v′:u′=x1w1v1∼zn−j:0≤j≤n−2∼yj:2≤j≤n−1∼xn−j:1≤j≤n−2∼wj:2≤j≤n−1∼vn−j:0≤j≤n−2∼w1v1wnxnyn=v′.Case 13:u′=x1 and v′=xi, 2≤i≤n.Case 13.1:i=2:(97)PHu′,v′:u′=x1∼yj:1≤j≤n−1∼zn−j:1≤j≤n−1∼znyn∼xn−j:0≤j≤n−3∼w3v3∼vjwj:4≤j≤n∼v1w1v2w2x2=v′.Case 13.2: 3≤i≤n−1:(98)PHu′,v′:u′=x1y1∼yjxj:2≤j≤i−1∼yj:i≤j≤n−1∼zn−j:1≤j≤n−1∼znyn∼xn−j:0≤j≤n−i−1∼wi+1vi+1∼vjwj:i+2≤j≤n∼vjwj:1≤j≤i∼xi=v′.Case 13.3: i=n:(99)PHu′,v′:u′=x1w1∼vj:1≤j≤n∼wn−j:0≤j≤n−2∼xj:2≤j≤n−1∼yn−j:1≤j≤n−1∼zj:1≤j≤n∼ynxn=v′.Case 14:u′=x1 and v′=wi, 1≤i≤n.Case 14.1:1≤i≤n−1:(100)PHu′,v′:u′=x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−i−1∼vj:i+1≤j≤n∼vjwj:1≤j≤i=v′.Case 14.2: i=n:(101)PHu′,v′:u′=x1w1∼vj:1≤j≤n∼wn−j:1≤j≤n−2∼xj:2≤j≤n−1∼yn−j:1≤j≤n−1∼zj:1≤j≤n∼ynxnwn=v′.Case 15:u′=x1 and v′=vi, 1≤i≤n.Case 15.1:1≤i≤n−1:(102)PHu′,v′:u′=x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−i∼vj:i+1≤j≤n∼vjwj:1≤j≤i−1∼vi=v′.Case 15.2: i=n:(103)PHu′,v′:u′=x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−1∼vj:1≤j≤n=v′.Case 16:u′=w1 and v′=zi, 1≤i≤n.Case 16.1:1≤i≤n−1:(104)PHu′,v′:u′=w1v1∼vn−j:0≤j≤n−2∼wj:2≤j≤n∼xn∼xj:1≤j≤i∼yi−j:0≤j≤i−1∼yn−j:0≤j≤n−i−1∼zj:i+1≤j≤n∼zj:1≤j≤i=v′.Case 16.2: i=n:(105)PHu′,v′:u′=w1∼vj:1≤j≤n∼wn−j:0≤j≤n−2∼xj:2≤j≤n∼yn−j:0≤j≤n−2∼x1y1∼zj:1≤j≤n=v′.Case 17:u′=w1 and v′=yi, 1≤i≤n.Case 17.1:1≤i≤n−1:(106)PHu′,v′:u′=w1wnv1∼vn−j:0≤j≤n−2∼wj:2≤j≤n−1∼xn−jyn−j:1≤j≤n−i−1∼xi−j:0≤j≤i−1∼xnyn∼zn−j:0≤j≤n−1∼yj:1≤j≤i=v′.Case 17.2: i=n:(107)PHu′,v′:u′=w1v1∼vn−j:0≤j≤n−2∼wj:2≤j≤n∼xn−j:0≤j≤n−1∼yj:1≤j≤n−1∼zn−j:1≤j≤n−1∼znyn=v′.Case 18:u′=w1 and v′=xi, 1≤i≤n.Case 18.1:1≤i≤n−1:(108)PHu′,v′:u′=w1v1∼vn−j:0≤j≤n−2∼wj:2≤j≤n∼xn−j:0≤j≤n−i−1∼yj:i+1≤j≤n∼zn−j:0≤j≤n−1∼yjxj:1≤j≤i=v′.Case 18.2:i=n:(109)PHu′,v′:u′=w1∼vj:1≤j≤n∼wn−j:0≤j≤n−2∼xj:2≤j≤n−1∼yn−j:1≤j≤n−2∼x1y1∼zj:1≤j≤n∼ynxn=v′.Case 19:u′=w1 and v′=wi, 2≤i≤n.Case 19.1:2≤i≤n−1:(110)PHu′,v′:u′=w1x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−i−1∼vj:i+1≤j≤n∼v1∼vjwj:2≤j≤i=v′.Case 19.2: i=n:(111)PHu′,v′:u′=w1x1y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−2∼wj:2≤j≤n−1∼vn−j:1≤j≤n−1∼vnwn=v′.Case 20:u′=w1 and v′=vi, 1≤i≤n.Case 20.1:i=1:(112)PHu′,v′:u′=w1x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−2∼vj:2≤j≤n∼v1=v′.Case 20.2: 2≤i≤n−1:(113)PHu′,v′:u′=w1x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−i∼vj:i+1≤j≤n∼v1∼vjwj:2≤j≤i−1∼vi=v′.Case 20.3: i=n:(114)PHu′,v′:u′=w1x1y1z1∼zn−j:0≤j≤n−2∼yj:2≤j≤n∼xn−j:0≤j≤n−2∼wj:2≤j≤n∼vj:1≤j≤n=v′.Case 21:u′=v1 and v′=zi, 1≤i≤n.Case 21.1:1≤i≤n−1:(115)PHu′,v′:u′=v1∼vn−j:0≤j≤n−2∼wj:1≤j≤n∼xn−j:0≤j≤n−i−1∼yj:i+2≤j≤n∼yjxj:1≤j≤i∼yi+1∼zj:i+1≤j≤n∼zj:1≤j≤i=v′.Case 21.2: i=n:(116)PHu′,v′:u′=vj:1≤j≤n∼wn−j:0≤j≤n−1∼xj:1≤j≤n∼yn−j:0≤j≤n−1∼zj:1≤j≤n=v′.Case 22:u′=v1 and v′=yi, 1≤i≤n.Case 22.1:1≤i≤n−1:(117)PHu′,v′:u′=v1∼vn−j:0≤j≤n−2∼wj:1≤j≤n∼xn−j:0≤j≤n−i∼yj:i+1≤j≤n∼zn−j:0≤j≤n−1∼yjxj:1≤j≤i−1∼yi=v′.Case 22.2: i=n:(118)PHu′,v′:u′=v1∼vn−j:0≤j≤n−2∼wj:1≤j≤n∼xn−j:0≤j≤n−1∼yj:1≤j≤n−1∼zn−j:1≤j≤n−1∼znyn=v′.Case 23:u′=v1 and v′=xi, 1≤i≤n.Case 23.1:1≤i≤n−1:(119)PHu′,v′:u′=v1∼vn−j:0≤j≤n−2∼wj:1≤j≤n∼xn−j:0≤j≤n−i−1∼yj:i+1≤j≤n∼zn−j:0≤j≤n−1∼yjxj:1≤j≤i=v′.Case 23.2: i=n:(120)PHu′,v′:u′=vj:1≤j≤n∼wn−j:0≤j≤n−1∼xj:1≤j≤n−1∼yn−j:1≤j≤n−1∼zj:1≤j≤n∼ynxn=v′.Case 24:u′=v1 and v′=wi, 1≤i≤n.Case 24.1:1≤i≤n−1:(121)PHu′,v′:u′=vjwj:1≤j≤i−1∼vj:i≤j≤n∼wn−j:0≤j≤n−i−1∼xj:i+1≤j≤n∼yn−j:0≤j≤n−2∼zj:2≤j≤n∼z1y1∼xj:1≤j≤i∼wi=v′.Case 24.2: i=n:(122)PHu′,v′:u′=v1∼vn−j:0≤j≤n−2∼wj:1≤j≤n−1∼xn−j:1≤j≤n−1∼yj:1≤j≤n−1∼zn−j:1≤j≤n−1∼znynxnwn=v′.Case 25:u′=v1 and v′=vi, 2≤i≤n.Case 25.1:2≤i≤n−1:(123)PHu′,v′:u′=v1∼vn−j:0≤j≤n−i−1∼wj:i≤j≤n∼xn−j:0≤j≤n−2∼yj:2≤j≤n∼zn−j:0≤j≤n−1∼y1x1∼wj−1vj:2≤j≤i=v′.Case 25.2: i=n:(124)PHu′,v′:u′=v1w1x1y1∼zj:1≤j≤n∼yn−j:0≤j≤n−2∼xj:2≤j≤n∼wn−j:0≤j≤n−2∼vj:2≤j≤n=v′.
Existence of Hamiltonian paths between any two vertices of then-dimensional convex polytope Kn completes the proof. □
Using Theorems1 and 4, the following proposition computes the detour index of Kn.Proposition 3.
LetG=Kn, where n≥3. Then the detour index of G is(125)ωG=5n5n−122.Proof.
The number of vertices in graphG is 5n. Replacing 5n with n in Theorem 1 completes the proof.


## 5. A Family of Non-Hamilton-connected Convex Polytopes

Forn≥4, by Bn, we denote the graph of convex polytope defined in [24] which consists of n number of 3-sided faces, 2n number of 4-sided faces, and n number of pentagonal faces, see Figure 4.Figure 4
The graph of convex polytopeBn.Mathematically, the vertex set ofBn consists of four layers of vertices, i.e., vi, wi, xi, yi, and zi. That is to say that VBn=vi,wi,xi,yi,zi:0≤i≤n−1. Accordingly, the edge set of Bn is as follows:(126)EBn=vivi+1,viwi,wiwi+1,wixi,wi+1xi,xiyi,yiyi+1,yizi,zizi+1:0≤i≤n−1.Note that arithmetics in the subscripts is performed modulon−1. Layer comprising vertices vi0≤i≤n−1 is called the first layer. Similarly, layers composed by vertices wi0≤i≤n−1, xi0≤i≤n−1, yi0≤i≤n−1, and zi0≤i≤n−1 are called second layer, third layer, fourth layer, and fifth layer, respectively. Note that first, second, fourth, and fifth layers form cycles of length n.The following result shows that the infinite familyBn of convex polytopes is non-Hamilton-connected.Theorem 5.
Then-dimensional convex polytope Bn, with n≥4, is non-Hamilton-connected.Proof.
It is enough to show that there exist two vertices in then-dimensional convex polytope Bn such that no Hamiltonian path exists between them.
It is easy to see that there exists no Hamiltonian path between any two vertices at distance two on the outer layer, i.e., betweenzi and zi+2 if n is even and between consecutive vertices on the outer layer, i.e., zi and zi+1 if n is odd, where 0≤i≤n−1 such that subscripts are taken modulo n−1. This shows that the n-dimensional convex polytope Bn is non-Hamilton-connected.


## 6. Conclusion

Determining whether or not a graph is Hamilton-connected is NP-complete graph. Thus, it is natural to study the Hamilton-connectivity of infinite families of graphs. In this paper, we have studied Hamilton-connectivity of certain infinite families of convex polytopes. We construct three infinite families of convex polytopes which have been shown to be Hamilton-connected. Moreover, one infinite family is shown to be non-Hamilton-connected which shows that not all the convex polytopes are Hamilton-connected. As a by-product, we compute the detour index of Hamilton-connected families of convex polytopes.As future directions, we propose the following problems:Problem 1.
Is there any other way to show Hamilton-connectivity of a given graph?Problem 2.
Baca [18] introduced a family Dn of convex polytopes. Determine whether Dn is Hamilton-connected.Problem 3.
Imran et al. [57] introduced the family Tn of convex polytopes. Determine whether or not Tn is Hamilton-connected.



---

*Source: 6684784-2021-01-25.xml*