The Hamiltonicity and Hamiltonian-connectivity of Solid Supergrid Graphs

被引：0
作者：
Fatemeh Keshavarz-Kohjerdi
Alireza Bagheri
机构：
[1] Shahed University,Department of Computer Science
[2] Amirkabir University of Technology (Tehran Polytechnic),Department of Computer Engineering
来源：
Bulletin of the Malaysian Mathematical Sciences Society | 2023年 / 46卷
关键词：
Hamiltonian path; Hamiltonian-connected; Hamiltonian cycle; Solid supergrid graph; 3-connected graph; 05C45; 05C40; 05C85;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
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.
引用
收藏
相关论文
共 57 条
[1]  
Arkin EM(2009)Not being (super)thin or solid is hard: a study of grid Hamiltonicity Comput. Geom. 42 582-605
[2]  
Fekete SP(2002)An efficient algorithm for constructing Hamiltonian paths in meshes Parallel Comput. 28 1293-1305
[3]  
Islam K(2008)Hamiltonian properties of triangular grid graphs Discret. Math. 308 6166-6188
[4]  
Meijer H(2015)The Hamiltonian properties of supergrid graphs Theor. Comput. Sci. 602 132-148
[5]  
Mitchell JSB(2016)Hamiltonian cycles in linear-convex supergrid graphs Discret. Appl. Math. 211 99-112
[6]  
Nunez-Rodriguez Y(2017)The Hamiltonian connectivity of rectangular supergrid graphs Discret. Optim. 26 41-65
[7]  
Polishchuk V(2017)The Hamiltonicity and Hamiltonian connectivity of some shaped supergrid graphs IAENG Intern. J. Comput. Sci. 44 432-444
[8]  
Rappaport D(2019)The Hamiltonian connectivity of alphabet supergrid graphs IAENG Intern. J. Appl. Math. 49 69-85
[9]  
Xiao H(1982)Hamiltonian paths in grid graphs SIAM J. Comput. 11 676-686
[10]  
Chen SD(2016)Hamiltonian paths in Theor. Comput. Sci. 621 37-56
123456