Hamiltonian cycles on Ammann-Beenker tilings

Singh, Shobhna, Lloyd, Jerome and Flicker, Felix 2024. Hamiltonian cycles on Ammann-Beenker tilings. Physical Review X 14 , 031005. 10.1103/PhysRevX.14.031005

PDF - Published Version Available under License Creative Commons Attribution. Download (2MB)

Abstract

We provide a simple algorithm for constructing Hamiltonian graph cycles (visiting every vertex exactly once) on a set of arbitrarily large finite subgraphs 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 traveling 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 three-coloring problem, giving ground states for the

Item Type:	Article
Date Type:	Publication
Status:	Published
Schools:	Physics and Astronomy
Publisher:	American Physical Society
ISSN:	2160-3308
Funders:	EPSRC
Date of First Compliant Deposit:	22 July 2024
Date of Acceptance:	1 May 2024
Last Modified:	22 Jul 2024 13:15
URI:	https://orca.cardiff.ac.uk/id/eprint/170810

Actions (repository staff only)

Edit Item