 Components of flip graphs of domino tilings in quadriculated cylinder and torusQianqian Liu, Jingfeng Wang, Chunmei Li and Heping Zhang Applied Mathematics and Computation, 2026, vol. 510, issue C Abstract: Let R be a quadriculated surface, possibly with boundary, consisting of unit squares, and each interior vertex being surrounded by 4 squares. A tiling of R is a placement of dominoes (a pair of adjacent squares) so that there are no gaps or overlaps. The flip graph of R is a graph whose vertices are all tilings of R and two tilings are adjacent if we can obtain one from another by a flip (90∘ rotation of a pair of side-by-side dominoes). By using graph-theoretical approach, we prove that the flip graph of 2m×(2n+1) quadriculated cylinder is still connected, but that of 2m×(2n+1) quadriculated torus consists of two isomorphic components. For a tiling t, we associate an integer, called forcing number, as the minimum number of dominoes in t that is contained in no other tilings. As a consequence, we obtain that the forcing numbers of all tilings in 2m×(2n+1) quadriculated cylinder and torus form respectively an integer interval whose maximum value is (n+1)m. Keywords: Domino; Tiling; Flip; Perfect matching; Resonance graph; Forcing spectrum; AMS subject classification:; 05C70; 05C40 (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:510:y:2026:i:c:s0096300325004230 DOI: 10.1016/j.amc.2025.129697 Access Statistics for this article Applied Mathematics and Computation is currently edited by Theodore Simos More articles in Applied Mathematics and Computation from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.