期刊名称：Lecture Notes in Engineering and Computer Science
印刷版ISSN：2078-0958
电子版ISSN：2078-0966
出版年度：2018
卷号：2233&2234
页码：117-122
出版社：Newswood and International Association of Engineers
摘要：Supergrid graphs include grid graphs and triangular
grid graphs as their subgraphs. The Hamiltonian path
problem for general supergrid graphs is a well-known NPcomplete
problem. A graph is called Hamiltonian connected
if there exists a Hamiltonian path between any two distinct
vertices. In the past, we verified the Hamiltonian connectivity
of some special supergrid graphs, including rectangular, triangular,
parallelogram, trapezoid, and alphabet supergrid graphs,
except few trivial conditions. In this paper, we will prove that
every L-shaped supergrid graph always contains a Hamiltonian
cycle except one trivial condition. We also present necessary and
sufficient conditions for the existence of a Hamiltonian path
between two given vertices in L-shaped supergrid graphs. The
Hamiltonian connectivity of L-shaped supergrid graphs can be
applied to compute the optimal stitching trace of computer
embroidering machines while a varied-sized letter L is sewed
into an object.
