Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index

Sakander Hayat, Asad Khan, Suliman Khan, Jia-Bao Liu and M. Irfan Uddin

Complexity, 2021, vol. 2021, 1-23

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.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/complexity/2021/6684784.pdf (application/pdf)
http://downloads.hindawi.com/journals/complexity/2021/6684784.xml (application/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:complx:6684784

DOI: 10.1155/2021/6684784

Access Statistics for this article

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