Finding Hamiltonian Paths between Two Given Vertices in Even-sized T-shaped Grid Graphs

One of the most popular problems in graph theory is the Hamiltonian path or cycle problem. This problem is NP-complete for general graphs and even some classes of graphs, including general grid graphs. In this paper, we study the problem of finding a Hamiltonian path between two given vertices s and t in even-sized T-shaped grid graphs, which is special case of grid graphs. This problem has many applications including in sweeping robots and in parallel processing. In this paper, first we give necessary conditions for the existence of Hamiltonian paths and cycles, then we present a linear-time algorithm for solving these problem.