We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
The Hamiltonicity and Hamiltonian-connectivity of Solid Supergrid Graphs.
- Authors
Keshavarz-Kohjerdi, Fatemeh; Bagheri, Alireza
- Abstract
The Hamiltonian path and cycle problems are well-known NP-complete problems. A given graph is Hamiltonian-connected if there exists a Hamiltonian path between any two vertices and is Hamiltonian if it has a Hamiltonian cycle. In this paper, we show that every 3-connected solid supergrid graph is Hamiltonian-connected and every 2-connected solid supergrid graph is Hamiltonian, and give linear-time algorithms for computing Hamiltonian cycles and paths in these graphs.
- Publication
Bulletin of the Malaysian Mathematical Sciences Society, 2023, Vol 46, Issue 3, p1
- ISSN
0126-6705
- Publication type
Article
- DOI
10.1007/s40840-023-01499-x