# On Hamilton-Connectivity and Detour Index of Certain Families of Convex Polytopes

Authors: Sakander Hayat; Muhammad Yasir Hayat Malik; Ali Ahmad; Suliman Khan; Faisal Yousafzai; Roslan Hasni
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

A convex polytope is the convex hull of a finite set of points in the Euclidean spaceℝn. By preserving the adjacency-incidence relation between vertices of a polytope, its structural graph is constructed. A graph is called Hamilton-connected if there exists at least one Hamiltonian path between any of its two vertices. The detour index is defined to be the sum of the lengths of longest distances, i.e., detours between vertices in a graph. Hamiltonian and Hamilton-connected graphs have diverse applications in computer science and electrical engineering, whereas the detour index has important applications in chemistry. Checking whether a graph is Hamilton-connected and computing the detour index of an arbitrary graph are both NP-complete problems. In this paper, we study these problems simultaneously for certain families of convex polytopes. We construct two infinite families of Hamilton-connected convex polytopes. Hamilton-connectivity is shown by constructing Hamiltonian paths between any pair of vertices. We then use the Hamilton-connectivity to compute the detour index of these families. A family of non-Hamilton-connected convex polytopes has also been constructed to show that not all convex polytope families are Hamilton-connected.


---

## Body

## 1. Introduction and Preliminaries

All graphs in this paper are simple, loopless, finite, and connected.A graphG is an ordered pair G=VG,EG with VG as its vertex set (i.e., set of points called vertices) and EG⊆VG2 as its edge set (i.e., set of lines connecting points called edges). The number of vertices, say n:=VG, is called the order of G and the number of edges, say m:=EG, is called the size of G. For two vertices x,y∈VG, we write x∼y if both x and y are adjacent, i.e., they are connected by an edge. For U⊆VG and x,y∈VG, if U=ui:1≤i≤p, then x∘ui:1≤i≤p∘y means that x∼u1 and up∼y and adjacency in the rest of ui’s 2≤i≤p stays the same. For a positive integer ν∈ℤ+, we write ν|2 (resp. ν∤2) if ν is even (resp. odd).A Hamiltonian cycleCHx in a connected graph G starting and finishing at the vertex x is a cycle traversing all the vertices of G. Similarly, a Hamiltonian path PHx,y between vertices x and y is the one covering the entire graph without missing any vertex. A graph comprising a Hamiltonian path (resp. Hamiltonian cycle) is called traceable (resp. Hamiltonian). Every Hamiltonian graph, by definition, is traceable, whereas the converse is not true in general. For instance, the so-called Petersen graph does not contain any Hamiltonian cycle and, thus, is not Hamiltonian. However, you can easily find a Hamiltonian path between two of its vertices, which makes it traceable but not Hamiltonian. Graphs comprising Hamiltonian paths between every pair of its vertices are called Hamilton-connected. They were introduced and studied in 1963 by Ore [1]. Trivalent Hamiltonian graphs and their canonical representation were studied by Frucht [2]. Hamilton-connectivity and Hamiltoniancity possess some extensive available literature. See, for example, [3–7].By preserving the vertex-edge incidence relation in convex polytopes, their graphs are constructed. Bača [8–10] was among the first researchers to consider these families of geometric graphs. In [10] (resp. [9]), Bača studied the problem of magic (resp. graceful and antigraceful) labeling of convex polytopes, whereas in [8], the problem of face antimagic labeling of convex polytopes was studied. Miller et al. [11] studied the vertex-magic total labeling of convex polytopes. Imran et al. [12–15] 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 and Sarwar [16] 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 [17]. Kratica et al. [18] 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. [19] (resp. Raza et al. [20]). The binary locating-dominating number of convex polytopes is studied by Simić et al. [21] and Raza et al. [22]. The open-locating-dominating number of certain convex polytopes has recently been studied by Savić et al. [23]. Hayat et al. [24] studied Hamilton-connectivity and detour index in convex polytopes.For a graphG, let ℓx,y be the length of the longest path (i.e., detour) between vertices x and y of G. The detour index [25] is defined to be the sum of the lengths of the detour 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.In chemistry, the detour index has diverse applications. Lukovits [26] put forward its QSAR/QSPR applications. Trinajstić et al. [27] presented some more of its chemical applications and compared its predictive potential in correlating the normal boiling points of benzenoid hydrocarbons with the performance of Wiener index. Rücker and Rücker [28] presented more of its rigorous applications for correlating the boiling points of acyclic and cyclic alkanes. The calculation of the detour index for a given graph has been shown an NP-complete problem in [29].Mahmiani et al. [30] proposed the edge versions of the detour index and studied their mathematical properties. Zhou and Cai [31] proved some upper and lower bounds on the detour index of graphs. Qi and Zhou [32] studied minimum uncyclic graphs with respect to the detour index. Du [33] studied the minimum detour index of bicyclic graphs. Fang et al. [34] characterized the minimum detour index of some families of tricyclic graphs. Karbasioun et al. [35] studied the applications of the detour index in infinite families of nanostar dendrimers. Wu and Deng [36] computed the detour index for a chain of C20 fullerenes. Kaladevi and Abinayaa [37] studied spectral properties of the detour index in relation with the Laplacian energy of graphs. Recently, Abdullah and Omar [38] introduced the restricted edge version of the detour index and studied it for some families of graphs. Tang et al. [39] studied Zagreb connection indices of some operation of graphs.LetSν denote the ν-dimensional star graph on ν+1 vertices. We end this section with an important and well-known result bounding the detour index in terms of its order.Theorem 1 [40].
LetG be an ν-vertex graph with ν≥3 and ωG be its detour index. Then,(2)ν−12≤ωG≤νν−122,with left equality if and only if G≅Sν, and right inequality holds if and only if G is Hamilton-connected.


## 2. A Family of Non-Hamilton-Connected Convex Polytopes

Bača [10] introduced the graph of convex polytope Dν for ν≥4. It is a family of convex polytopes comprising 2ν pentagonal faces. See Figure 1 for the ν-dimensional family of convex polytopes Dν.Figure 1
The graph of convex polytopeDν.Mathematically, the vertex set ofDν consists of four layers of vertices, i.e., wp, xp, yp, and zp. That is to say that VDν=wp,xp,yp,zp:1≤p≤ν. Accordingly, the edge set of Dν is as follows:(3)EDν=wpwp+1,zpzp+1,wpxp,xpyp,xp+1yp,ypzp:1≤p≤ν.The subscripts are to be considered moduloν. The layer of vertices comprising wp is called the inner layer, whereas the layer comprising zp is called the outer layer of Dν. The vertices xp and yp,1≤p≤ν form the middle layers.The following result shows that the infinite familyDν of convex polytopes is not Hamilton-connected.Proposition 1.
Theν-dimensional convex polytope Dν, with ν≥4, is non-Hamilton-connected.Proof.
It is enough to show that there exist two vertices in theν-dimensional convex polytope Dν such that no Hamiltonian path exists between them.
It is easy to see that, between every pair of vertices at distance two on the outer layer, i.e., betweenzp and zp+21≤p≤ν−1, there exists no Hamiltonian path because of the two pentagonal layers of faces. This shows that the ν-dimensional convex polytope Dν is non-Hamilton-connected.


## 3. Hamilton-Connectivity and the Detour Index ofHν

In this section, we show that the graph ofν-dimensional convex polytope Hν is Hamilton-connected. Then, we use its Hamilton-connectivity to find a formula for its detour index. This family of convex polytopes was introduced by Imran and Siddiqui [14].Mathematically, the vertex set ofHν consists of four layers of vertices, i.e., vp, wp, xp, yp, and zp. That is to say that VHν=vp,wp,xp,yp,zp:1≤p≤ν. Accordingly, the edge set of Hν is as follows:(4)EHν=vpvp+1,vpwp,wpvp+1,wpwp+1,wpxp,xpxp+1,xpyp,ypxp+1,ypyp+1,ypzp,zpzp+1:1≤p≤ν.The subscripts are to be considered moduloν. See Figure 2 to view the ν-dimensional convex polytope graph Hν.Figure 2
Theν-dimensional convex polytope Hν.The following is the main result of this section.Theorem 2.
The graph ofν-dimensional convex polytope Hν, with ν≥5, is Hamilton-connected.Proof.
We prove this result by definition. For this, we have to show that there exist Hamiltonian paths between any pair of vertices ofHν.
LetPHu,v be a Hamiltonian path between vertices u and v in Hν. Let VHν=Z∪Y∪X∪W∪V such that Z=z1,z2,…,zν, Y=y1,y2,…,yν,X=x1,x2,…,xν, W=w1,w2,…,wν, and V=v1,v2,…,vν (see Figure 2).Case 1:u′=z1 and v′=zp,2≤p≤νSubcase 1.1:2≤p≤ν−2:(5)PHu′,v′:u′=z1∘zν−q:0≤q≤ν−p−1∘yp−q+1:0≤q≤p−2∘xq:3≤q≤p+1∘xqyq:p+2≤q≤ν∘y1x1w1∘vq:1≤q≤ν∘wν−q:0≤q≤ν−2∘x2y2∘zq:2≤q≤p=v′.Subcase 1.2:p=ν−1:(6)PHu′,v′:u′=z1zνyνy1x1w1∘yq:1≤q≤ν∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν∘yν−q:1≤q≤ν−2∘zq:2≤q≤ν−1=v′.Subcase 1.3:p=ν:(7)PHu′,v′:u′=z1y1x1w1∘vq:1≤q≤ν∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν∘yν−q:0≤q≤ν−2∘zq:2≤q≤ν=v′.Case 2:u′=z1 and v′=yp,1≤p≤νSubcase 2.1:1≤p≤ν−1:(8)PHu′,v′:u′=zq:1≤q≤ν∘yν−q:0≤q≤ν−p−1∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν∘v1w1∘xqyq:1≤q≤p=v′.Subcase 2.2:p=ν:(9)PHu′,v′:u′=z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν−1∘xν−q:0≤q≤ν−2∘wq:2≤q≤ν∘vν−q:0≤q≤ν−1∘w1x1y1yν=v′.Case 3:u′=z1 and v′=xp,1≤p≤νSubcase 3.1:1≤p≤ν−1:(10)PHu′,v′:u′=zq:1≤q≤ν∘yν−q:0≤q≤ν−p∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν∘v1w1∘xqyq:1≤q≤p−1∘xp=v′.Subcase 3.2:p=ν:(11)PHu′,v′:u′=zq:1≤q≤ν∘yν−q:0≤q≤ν−1∘xq:1≤q≤ν−1∘wν−q:1≤q≤ν−1∘vq:1≤q≤ν∘wνxν=v′.Case 4:u′=z1 and v′=wp,1≤p≤νSubcase 4.1:1≤p≤ν−1:(12)PHu′,v′:u′=zq:1≤q≤ν∘yν−q:0≤q≤ν−1∘xq:1≤q≤ν∘wν−q:0≤q≤ν−p−1∘vq:p+1≤q≤ν∘vqwq:1≤q≤p=v′.Subcase 4.2:p=ν:(13)PHu′,v′:u′=zq:1≤q≤ν∘yν−q:0≤q≤ν−1∘x1∘xν−q:0≤q≤ν−2∘wq:2≤q≤ν−1∘vν−q:0≤q≤ν−1∘v1wν=v′.Case 5:u′=z1 and v′=vp,1≤p≤ν(14)PHu′,v′:u′=zq:1≤q≤ν∘yν−q:0≤q≤ν−1∘xq:1≤q≤ν∘wν−q:0≤q≤ν−p∘vq:p+1≤q≤ν∘vqwq:1≤q≤p−1∘vp=v′.Case 6:u′=y1 and v′=zp,1≤p≤νSubcase 6.1:1≤p≤ν−1:(15)PHu′,v′:u′=y1x1w1∘vq:1≤q≤ν∘wν−q:0≤q≤ν−2∘xqyq:2≤q≤p∘xq:p+1≤q≤ν∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p=v′.Subcase 6.2:p=ν:(16)PHu′,v′:u′=y1∘zq:1≤q≤ν−1∘yν−q:1≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν∘v1w1x1yνzν=v′.Case 7:u′=y1 and v′=yp,2≤p≤νSubcase 8.1:2≤p≤ν−1:(17)PHu′,v′:u′=y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−p−1∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν∘v1w1x1∘xqyq:2≤q≤p=v′.Subcase 8.2:p=ν:(18)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν−1∘xν−q:1≤q≤ν−1∘wq:1≤q≤ν−1∘vν−q:1≤q≤ν−1∘vνwνxνyν=v′.Case 8:u′=y1 and v′=xp,1≤p≤νSubcase 8.1:p=1:(19)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xν−q:0≤q≤ν−2∘wq:2≤q≤ν∘vν−q:0≤q≤ν−2∘v1w1x1=v′.Subcase 8.2:2≤p≤ν−1:(20)PHu′,v′:u′=y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−p∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν∘v1w1x1∘xqyq:2≤q≤p−1∘xp=v′.Subcase 8.3:p=ν:(21)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xq:1≤q≤ν−1∘wν−q:1≤q≤ν−1∘vq:1≤q≤ν∘wνxν=v′.Case 9:u′=y1 and v′=wp,1≤p≤νSubcase 9.1:1≤p≤ν−1:(22)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xq:1≤q≤ν∘wν−q:0≤q≤ν−p−1∘vq:p+1≤q≤ν∘vqwq:1≤q≤p=v′.Subcase 9.2:p=ν:(23)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xν−q:0≤q≤ν−1∘wq:1≤q≤ν−1∘vν−q:1≤q≤ν−1∘vνwν=v′.Case 10:u′=y1 and v′=vp,1≤p≤νSubcase 10.1:1≤p≤ν−1:(24)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xq:1≤q≤ν∘wν−q:0≤q≤ν−p∘vq:p+1≤q≤ν∘v1∘wqvq+1:1≤q≤p−1=v′.Subcase 10.2:p=ν:(25)PHu′,v′:u′=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xq:1≤q≤ν∘wν−q:0≤q≤ν−1∘vq:1≤q≤ν=v′.Case 11:u′=x1 and v′=zp,1≤p≤νSubcase 11.1:1≤p≤ν−1:(26)PHu′,v′:u′=x1w1v1∘vν−q:0≤q≤ν−2∘wq:2≤q≤ν∘xν−q:0≤q≤ν−p−1∘yp−qxp−q:0≤q≤p−2∘y1∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p=v′.Subcase 11.2:p=ν:(27)PHu′,v′:u′=xq:1≤q≤ν−1∘wν−q:1≤q≤ν−1∘vq:1≤q≤ν∘wνxν∘yν−q:0≤q≤ν−1∘zq:1≤q≤ν=v′.Case 12:u′=x1 and v′=yp,2≤p≤νSubcase 12.1:1≤p≤ν−1:(28)PHu′,v′:u′=x1w1v1∘vqwq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yq:p+1≤q≤ν∘zν−q:0≤q≤ν−1∘y1∘xqvq:2≤q≤p=v′.Subcase 12.2:p=ν:(29)PHu′,v′:u′=x1w1v1∘vqwq:2≤q≤ν∘xν−q:0≤q≤ν−2∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyν=v′.Case 13:u′=x1 and v′=xp,2≤p≤νSubcase 13.1:2≤p≤ν−1:(30)PHu′,v′:u′=x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−p∘yp−qxp−q:1≤q≤p−1∘xν−q:0≤q≤ν−p−1∘wq:p+1≤q≤ν∘vν−q:0≤q≤ν−1∘wq:1≤q≤p∘xp=v′.Subcase 13.2:p=ν:(31)PHu′,v′:u′=x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν−1∘wν−q:1≤q≤ν−1∘wq:1≤q≤ν∘wνxν=v′.Case 14:u′=x1 and v′=wp,1≤p≤νSubcase 14.1:1≤p≤ν−1:(32)PHu′,v′:u′=x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−p−1∘vq:p+1≤q≤ν∘vqwq:1≤q≤p=v′.Subcase 14.2:p=ν:(33)PHu′,v′:u′=x1y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xν−q:0≤q≤ν−2∘wq:2≤q≤ν−1∘vν−q:0≤q≤ν−1∘w1wν=v′.Case 15:u′=x1 and v′=vp,1≤p≤νSubcase 15.1:1≤p≤ν−1:(34)PHu′,v′:u′=x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−p∘vq:p+1≤q≤ν∘vqwq:1≤q≤p−1∘vp=v′.Subcase 15.2:p=ν:(35)PHu′,v′:u′=x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−1∘vq:1≤q≤ν=v′.Case 16:u′=w1 and v′=zp,1≤p≤νSubcase 16.1:1≤p≤ν−1:(36)PHu′,v′:u′=w1v1∘vν−q:0≤q≤ν−2∘wq:2≤q≤ν∘xν−q:0≤q≤ν−p∘yq:p≤q≤ν∘xqyq:1≤q≤p−1∘zp−q:1≤q≤p−1∘zν−q:0≤q≤ν−p=v′.Subcase 16.2:p=ν:(37)PHu′,v′:u′=w1∘vq:1≤q≤ν∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν∘x1∘yν−q:0≤q≤ν−1∘zq:1≤q≤ν=v′.Case 17:u′=w1 and v′=yp,1≤p≤νSubcase 17.1:1≤p≤ν−1:(38)PHu′,v′:u′=w1v1∘vν−q:0≤q≤ν−2∘wq:2≤q≤ν∘xν−q:0≤q≤ν−p∘yp−qxp−q:1≤q≤p−1∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p∘yp=v′.Subcase 17.2:p=ν:(39)PHu′,v′:u′=w1v1∘vν−q:0≤q≤ν−2∘wq:2≤q≤ν∘xν−q:0≤q≤ν−1∘yν−q:0≤q≤ν−1∘zq:1≤q≤ν=v′.Case 18:u′=w1 and v′=xp,1≤p≤νSubcase 18.1:1≤p≤ν−1:(40)PHu′,v′:u′=w1v1∘vν−q:0≤q≤ν−2∘wq:2≤q≤ν∘xν−q:0≤q≤ν−p−1∘yq:p+1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyν∘xqyq:1≤q≤p−1∘xp=v′.Subcase 18.2:p=ν:(41)PHu′,v′:u′=w1∘vq:1≤q≤ν∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν−1∘yν−q:1≤q≤ν−1∘zq:1≤q≤ν∘yνx1xν=v′.Case 19:u′=w1 and v′=wp,2≤p≤νSubcase 19.1:2≤p≤ν−1:(42)PHu′,v′:u′=w1x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−p−1∘vq:p+1≤q≤ν∘vqwq:1≤q≤p=v′.Subcase 19.2:p=ν:(43)PHu′,v′:u′=w1x1y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xν−q:0≤q≤ν−2∘wq:2≤q≤ν−1∘vν−q:0≤q≤ν−1∘vνwν=v′.Case 20:u′=w1 and v′=vp,1≤p≤νSubcase 20.1:p=1:(44)PHu′,v′:u′=w1x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν∘v1=v′.Subcase 20.2:2≤p≤ν−1:(45)PHu′,v′:u′=w1x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−p∘vq:p+1≤q≤ν∘vqwq:1≤q≤p−1∘vp=v′.Subcase 20.3:p=ν:(46)PHu′,v′:u′=w1∘vq:1≤q≤ν−1∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν−1∘yν−q:1≤q≤ν−1∘zq:1≤q≤ν∘yνx1xνwνvν=v′.Case 21:u′=v1 and v′=zp,1≤p≤νSubcase 21.1:p=1:(47)PHu′,v′:u′=vq:1≤q≤ν∘wν−q:0≤q≤ν−1∘x1∘xν−q:0≤q≤ν−2∘wq:1≤q≤ν∘zν−q:0≤q≤ν−1=v′.Subcase 21.2:2≤p≤ν−1:(48)PHu′,v′:u′=vq:1≤q≤ν∘wν−q:0≤q≤ν−1∘xqyq:1≤q≤p−2∘xq:p−1≤q≤ν∘yν−q:0≤q≤ν−p+1∘zp−q:1≤q≤p−1∘zν−q:0≤q≤ν−p=v′.Subcase 21.3:p=ν:(49)PHu′,v′:u′=vq:1≤q≤ν∘wν−q:0≤q≤ν−1∘xq:1≤q≤ν∘yν−q:0≤q≤ν−1∘zq:1≤q≤ν=v′.Case 22:u′=v1 and v′=yp,1≤p≤νSubcase 22.1:1≤p≤ν−1:(50)PHu′,v′:u′=vq:1≤q≤ν∘wν−q:0≤q≤ν−1∘xqyq:1≤q≤p−1∘xq:p≤q≤ν∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p=v′.Subcase 22.2:p=ν:(51)PHu′,v′:u′=vq:1≤q≤ν∘wν−q:0≤q≤ν−1∘xν−q:0≤q≤ν−1∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyν=v′.Case 23:u′=v1 and v′=xp,1≤p≤νSubcase 23.1:1≤p≤ν−1:(52)PHu′,v′:u′=v1∘vν−q:0≤q≤ν−2∘wq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yq:p≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyν∘xqyq:1≤q≤p−1∘xp=v′.Subcase 23.2:p=ν:(53)PHu′,v′:u′=vq:1≤q≤ν∘wν−q:0≤q≤ν−1∘xq:1≤q≤ν−1∘yν−q:1≤q≤ν−1∘zq:1≤q≤ν∘yνxν=v′.Case 24:u′=v1 and v′=wp,1≤p≤νSubcase 24.1:1≤p≤ν−1:(54)PHu′,v′:u′=vqwq:1≤q≤p−1∘vq:p≤q≤ν∘wν−q:0≤q≤ν−p−1∘xq:p+1≤q≤ν∘yν−q:0≤q≤ν−2∘zq:2≤q≤ν∘z1y1∘xq:1≤q≤p∘wp=v′.Subcase 24.2:p=ν:(55)PHu′,v′:u′=v1∘vν−q:0≤q≤ν−2∘wq:1≤q≤ν−1∘xν−q:0≤q≤ν−1∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyνxνwν=v′.Case 25:u′=v1 and v′=vp,2≤p≤νSubcase 25.1:2≤p≤ν−1:(56)PHu′,v′:u′=v1w1x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−qvν−q:0≤q≤ν−p−1∘wp−q:0≤q≤p−2∘vq:2≤q≤p=v′.Subcase 25.2:p=ν:(57)PHu′,v′:u′=v1w1x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−2∘vq:2≤q≤ν=v′.
The existence of the Hamiltonian path between every pair of vertices of theHν completes the proof.
Using Theorems1 and 2, the following proposition computes the detour index of Hν.Corollary 1.
LetG=Hν, where ν≥4. Then, the detour index of G is(58)ωG=5ν5ν−122.Proof.
The number of vertices in the graphG is 5ν. Replacing 5ν with n in Theorem 1 gives the proposition.


## 4. Hamilton-Connectivity and the Detour Index ofGν

In this section, we show that the graphGν is Hamilton-connected. Afterwards, we use the Hamilton-connectivity to find the analytical exact expression of the detour index of the graph Gν.The vertex set ofGν consists of four layers of vertices, i.e., wp, xp, yp, and zp. That is to say that VGν=wp,xp,yp,zp:1≤p≤ν. Accordingly, the edge set of Gν is as follows:(59)EGν=wpwp+1,xpxp+1,ypyp+1,zpzp+1,wpxp,xpyp,ypxp+1,ypzp:1≤p≤ν−1.The subscripts are to be considered moduloν. Figure 3 presents the ν-dimensional convex polytope Gν with proper labeling of vertices which will be used to show its Hamilton-connectivity.Figure 3
Theν-dimensional convex polytope Gν.The following is the main result of this section.Theorem 3.
The graphν-dimensional convex polytope Gν, with ν≥5, is Hamilton-connected.Proof.
We prove this result by definition. For this, we have to show that there exist Hamiltonian paths between any pair of vertices ofGν.
LetPHu,v be a Hamiltonian path between vertices u and v in Gν. Let Gν=Z∪Y∪X∪W such that Z=z1,z2,…,zν, Y=y1,y2,…,yν, X=x1,x2,…,xν, and W=w1,w2,…,wν (see Figure 3).Case 1:u=z1 and v=zp,2≤p≤νSubcase 1.1:2≤p≤ν−2:(60)PHu,v:u=z1∘zν−q:0≤q≤ν−p−1∘yp−q+1:0≤q≤p−2∘xq:3≤q≤p+1∘xqyq:p+2≤q≤ν∘y1x1w1∘wν−q:0≤q≤ν−2∘x2y2∘zq:2≤q≤p=v.Subcase 1.2:p=ν−1:(61)PHu,v:u=z1zν∘yν−q:0≤q≤ν−3∘xq:3≤q≤ν∘wν−q:0≤q≤ν−1∘x1y1x2y2∘zq:2≤q≤ν−1=v.Subcase 1.3:p=ν:(62)PHu,v:u=z1y1x1w1∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν∘yν−q:0≤q≤ν−2∘zq:2≤q≤ν=v.Case 2:u=z1 and v=yp,1≤p≤νSubcase 2.1:1≤p≤ν−1:(63)PHu,v:u=zq:1≤q≤ν∘yν−q:0≤q≤ν−p−1∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−1∘xqyq:1≤q≤p=v.Subcase 2.2:p=ν:(64)PHu,v:u=z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν−1∘xν−q:1≤q≤ν−2∘y1x1∘wq:1≤q≤ν∘xνyν=v.Case 3:u=z1 and v=xp,1≤p≤νSubcase 3.1:1≤p≤ν−1:(65)PHu,v:u=z1∘zq:2≤q≤ν∘yν−q:0≤q≤ν−p∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−1∘xqyq:2≤q≤p−1∘xp=v.Subcase 3.2:p=ν:(66)PHu,v:u=zq:1≤q≤ν∘yν−q:0≤q≤ν−1∘xq:1≤q≤ν−1∘wν−q:1≤q≤ν−1∘wνxν=v.Case 4:u=z1 and v=wp,1≤p≤νSubcase 4.1:p=1:(67)PHu,v:u=zq:1≤q≤ν∘yν−q:0≤q≤ν−1∘xq:1≤q≤ν∘wν−q:0≤q≤ν−1=v.Subcase 4.2:2≤p≤ν:(68)PHu,v:u=zq:1≤q≤ν∘yν−q:0≤q≤ν−p+1∘xq:p≤q≤ν∘xqyq:1≤q≤p−2∘xp−1∘wp−q:1≤q≤p−1∘wν−q:0≤q≤ν−p=v.Case 5:u=y1 and v=zp,1≤p≤νSubcase 5.1:1≤p≤ν−1:(69)PHu,v:u=y1x1w1∘wν−q:0≤q≤ν−2∘xqyq:2≤q≤p∘xq:p+1≤q≤ν∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p=v.Subcase 5.2:p=ν:(70)PHu,v:u=y1∘zq:1≤q≤ν−1∘yν−q:1≤q≤ν−2∘xq:2≤q≤ν−1∘wν−q:1≤q≤ν−1∘wνxνx1yνzν=v.Case 6:u=y1 and v=yp,2≤p≤νSubcase 6.1:2≤p≤ν−1:(71)PHu,v:u=y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−p−1∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−1∘x1∘xqyq:2≤q≤p=v.Subcase 6.2:p=ν:(72)PHu,v:u=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν−1∘xν−q:1≤q≤ν−1∘wq:1≤q≤ν∘xνyν=v.Case 7:u=y1 and v=xp,1≤p≤νSubcase 7.1:p=1:(73)PHu,v:u=y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−1∘x1=v.Subcase 7.2:2≤p≤ν−1:(74)PHu,v:u=y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−p∘xq:p+1≤q≤ν∘wν−q:0≤q≤ν−1∘x1∘xqyq:2≤q≤p−1∘xp=v.Subcase 7.3:p=ν:(75)PHu,v:u=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xq:1≤q≤ν−1∘wν−q:1≤q≤ν−1∘wνxν=v.Case 8:u=y1 and v=wp,1≤p≤νSubcase 8.1:p=1:(76)PHu,v:u=y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤ν∘xq:1≤q≤ν∘wν−q:0≤q≤ν−1=v.Subcase 8.2:2≤p≤ν−1:(77)PHu,v:u=y1x1∘xqyq:2≤q≤p∘zp−q:0≤q≤p−1∘zν−q:0≤q≤ν−p−1∘yq:p+1≤q≤ν∘xν−q:0≤q≤ν−p−1∘wq:p+1≤q≤ν∘wq:1≤q≤p=v.Subcase 8.3:p=ν:(78)PHu,v:u=y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘x1∘wq:1≤q≤ν=v.Case 9:u=x1 and v=zp,1≤p≤νSubcase 9.1:1≤p≤ν−1:(79)PHu,v:u=x1∘wq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yp−qxp−q:0≤q≤p−2∘y1∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p=v.Subcase 9.2:p=ν:(80)PHu,v:u=x1∘wq:1≤q≤ν∘xν−q:0≤q≤ν−2∘yq:2≤q≤ν∘y1∘zq:1≤q≤ν=v.Case 10:u=x1 and v=yp,1≤p≤νSubcase 10.1:1≤p≤ν−1:(81)PHu,v:u=x1∘wq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yq:p+1≤q≤ν∘zν−q:0≤q≤ν−1∘y1∘xqyq:2≤q≤p=v.Subcase 10.2:p=ν:(82)PHu,v:u=x1∘wq:1≤q≤ν∘xν−q:0≤q≤ν−2∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyν=v.Case 11:u=x1 and v=xp,2≤p≤νSubcase 11.1:2≤p≤ν−1:(83)PHu,v:u=x1∘wq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yq:p≤q≤ν∘zν−q:0≤q≤ν−1∘yq−1xq:2≤q≤p=v.Subcase 11.2:p=ν:(84)PHu,v:u=x1w1∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν−1∘yν−q:1≤q≤ν−1∘zq:1≤q≤ν∘yνxν=v.Case 12:u=x1 and v=wp,1≤p≤νSubcase 12.1:p=1:(85)PHu,v:u=x1y1∘zq:1≤q≤ν∘yν−q:0≤q≤ν−2∘xq:2≤q≤ν∘wν−q:0≤q≤ν−1=v.Subcase 12.2:2≤p≤ν−1:(86)PHu,v:u=x1∘yq−1xq:2≤q≤p−1∘wp−q:1≤q≤p−1∘wν−q:0≤q≤ν−p−1∘xq:p+1≤q≤ν∘yν−q:0≤q≤ν−p∘zq:p≤q≤ν∘zq:1≤q≤p−1∘yp−1xpwp=v.Subcase 12.3:p=ν:(87)PHu,v:u=x1∘wq:1≤q≤ν−1∘xν−q:1≤q≤ν−2∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyνxνwν=v.Case 13:u=w1 and v=zp,1≤p≤νSubcase 13.1:1≤p≤ν−1:(88)PHu,v:u=wq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yp−qxp−q:0≤q≤p−1∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p=v.Subcase 13.2:p=ν:(89)PHu,v:u=wq:1≤q≤ν∘xν−q:0≤q≤ν−1∘yν−q:0≤q≤ν−1∘zq:1≤q≤ν=v.Case 14:u=w1 and v=yp,1≤p≤νSubcase 14.1:1≤p≤ν−1:(90)PHu,v:u=wq:1≤q≤ν∘xν−q:0≤q≤ν−p∘yp−qxp−q:1≤q≤p−1∘yν−q:0≤q≤ν−p−1∘zq:p+1≤q≤ν∘zq:1≤q≤p∘yp=v.Subcase 14.2:p=ν:(91)PHu,v:u=wq:1≤q≤ν∘xν−q:0≤q≤ν−1∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyν=v.Case 15:u=w1 and v=xp,1≤p≤νSubcase 15.1:p=1:(92)PHu,v:u=wq:1≤q≤ν∘xν−q:0≤q≤ν−2∘yq:2≤q≤ν∘zν−q:0≤q≤ν−1∘y1x1=v.Subcase 15.2:2≤p≤ν−1:(93)PHu,v:u=wq:1≤q≤ν∘xν−q:0≤q≤ν−p−1∘yq:p≤q≤ν∘zν−q:0≤q≤ν−1∘y1x1∘xqyq:2≤q≤p−1∘xp=v.Subcase 15.3:p=ν:(94)PHu,v:u=w1∘wν−q:0≤q≤ν−2∘xq:2≤q≤ν−1∘yν−q:1≤q≤ν−1∘zq:1≤q≤ν∘yνx1xν=v.Case 16:u=w1 and v=wp,2≤p≤νSubcase 16.1:2≤p≤ν−1:(95)PHu,v:u=w1∘wν−q:0≤q≤ν−p−1∘xqyq:p+1≤q≤ν∘x1y1z1∘zν−q:0≤q≤ν−2∘yq:2≤q≤p∘xp−q:0≤q≤p−2∘wq:2≤q≤p=v.Subcase 16.2:p=ν:(96)PHu,v:u=wq:1≤q≤ν−1∘xν−q:1≤q≤ν−1∘yq:1≤q≤ν−1∘zν−q:1≤q≤ν−1∘zνyνxνwν=v.
The existence of the Hamiltonian path between every pair of vertices of theGν completes the proof.
Using Theorems1 and 3, the following proposition computes the detour index of Gν.Corollary 2.
LetG=Gν, where ν≥4. Then, the detour index of G is(97)ωG=4ν4ν−122.Proof.
The number of vertices in the graphG is 4ν. Replacing 4ν with n in Theorem 1 gives the proposition.


## 5. 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. In this paper, we construct three infinite families of Hamilton-connected convex polytope networks. Furthermore, we construct an infinite family of non-Hamilton-connected convex polytope networks. The later construction shows that not all convex polytope networks are Hamilton-connected. 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 by Alspach and Liu [41], we propose the following conjectures [41]:Conjecture 1.
(i)
The generalized Petersen graphGPν,4ν≥9 is nonbipartite Hamilton-connected(ii)
The generalized Petersen graphGPν,5ν≥11 is nonbipartite Hamilton-connected if ν|2 and bipartite Hamilton-laceable if ν∤2



---

*Source: 5553216-2021-07-19.xml*