Title: Hamiltonian cycles on Ammann-Beenker Tilings

Abstract: We provide a simple algorithm for constructing Hamiltonian graph cycles (visiting every vertex exactly once) on the set of aperiodic two-dimensional Ammann-Beenker (AB) tilings. Using this result, and the discrete scale symmetry of AB tilings, we find exact solutions to a range of other problems which lie in the complexity class NP-Complete for general graphs. These include the equal-weight travelling salesperson problem, providing for example the most efficient route a scanning tunneling microscope tip could take to image the atoms of physical quasicrystals with AB symmetries; the longest path problem, whose solution demonstrates that collections of flexible molecules of any length can adsorb onto AB quasicrystal surfaces at density one, with possible applications to catalysis; and the 3-colouring problem, giving ground states for the $q$-state Potts model ($q\ge 3$) of magnetic interactions defined on the planar dual to AB, which may provide useful models for protein folding.