English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

Finding Hamitonian Cycles in square grid graphs is a well studied andimportant questions. More recent work has extended these results to triangularand hexagonal grids, as well as further restricted versions. In this paper, weexamine a class of more complex grids, as well as looking at the problem withrestricted types of paths. We investigate the hardness of Hamiltonian cycleproblem in grid graphs of semiregular tessellations. We give NP-hardnessreductions for finding Hamiltonian paths in grid graphs based on all eight ofthe semiregular tessilations. Next, we investigate variations on the problem offinding Hamiltonian Paths in grid graphs when the path is forced to turn atevery vertex. We give a polynomial time algorithm for deciding if a square gridgraph admits a Hamiltonian cycle which turns at every vertex. We then showdeciding if cubic grid graphs, even if the height is restricted to $2$, admit aHamiltonian cycle is NP-complete.

The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations