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

Sakander Hayat, Muhammad Yasir Hayat Malik, Ali Ahmad, Suliman Khan, Faisal Yousafzai and Roslan Hasni

Mathematical Problems in Engineering, 2021, vol. 2021, 1-18

Abstract:

A convex polytope is the convex hull of a finite set of points in the Euclidean space . 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.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/MPE/2021/5553216.pdf (application/pdf)
http://downloads.hindawi.com/journals/MPE/2021/5553216.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:jnlmpe:5553216

DOI: 10.1155/2021/5553216

Access Statistics for this article

More articles in Mathematical Problems in Engineering from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().