Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index
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 engi...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2021-01-01
|
| Series: | Complexity |
| Online Access: | http://dx.doi.org/10.1155/2021/6684784 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832550164119683072 |
|---|---|
| author | Sakander Hayat Asad Khan Suliman Khan Jia-Bao Liu |
| author_facet | Sakander Hayat Asad Khan Suliman Khan Jia-Bao Liu |
| author_sort | Sakander Hayat |
| collection | DOAJ |
| description | 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. |
| format | Article |
| id | doaj-art-be86b31db68744f2a71b23ac8cb3c93f |
| institution | Kabale University |
| issn | 1076-2787 1099-0526 |
| language | English |
| publishDate | 2021-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Complexity |
| spelling | doaj-art-be86b31db68744f2a71b23ac8cb3c93f2025-02-03T06:07:37ZengWileyComplexity1076-27871099-05262021-01-01202110.1155/2021/66847846684784Hamilton Connectivity of Convex Polytopes with Applications to Their Detour IndexSakander Hayat0Asad Khan1Suliman Khan2Jia-Bao Liu3Faculty of Engineering Sciences, GIK Institute of Engineering Sciences and Technology, Topi, Swabi, Khyber Pakhtunkhwa 23460, PakistanSchool of Computer Science and Cyber Engineering, Guangzhou University, Guangzhou 510006, ChinaFaculty of Engineering Sciences, GIK Institute of Engineering Sciences and Technology, Topi, Swabi, Khyber Pakhtunkhwa 23460, PakistanSchool of Mathematics and Physics, Anhui Jianzhu University, Hefei, Anhui 230000, ChinaA 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.http://dx.doi.org/10.1155/2021/6684784 |
| spellingShingle | Sakander Hayat Asad Khan Suliman Khan Jia-Bao Liu Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index Complexity |
| title | Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index |
| title_full | Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index |
| title_fullStr | Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index |
| title_full_unstemmed | Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index |
| title_short | Hamilton Connectivity of Convex Polytopes with Applications to Their Detour Index |
| title_sort | hamilton connectivity of convex polytopes with applications to their detour index |
| url | http://dx.doi.org/10.1155/2021/6684784 |
| work_keys_str_mv | AT sakanderhayat hamiltonconnectivityofconvexpolytopeswithapplicationstotheirdetourindex AT asadkhan hamiltonconnectivityofconvexpolytopeswithapplicationstotheirdetourindex AT sulimankhan hamiltonconnectivityofconvexpolytopeswithapplicationstotheirdetourindex AT jiabaoliu hamiltonconnectivityofconvexpolytopeswithapplicationstotheirdetourindex |