2022/11/20 by Qianqian Liu, Liu, Qianqian, Jingfeng Wang +5
Computer Science · Engineering · Materials Science · #Cellular Automata and Applications #Combinatorics (math.CO) #FOS: Mathematics #Quasicrystal Structures and Properties #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2211.10935
openalex publication_date 2022/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a region R consisting of unit squares, a domino is the union of two adjacent squares and a (domino) tiling is a collection of dominoes with disjoint interior whose union is the region. The flip graph T(R) is defined on the set of all tilings of R such that two tilings are adjacent if we change one to another by a flip (a 90∘ rotation of a pair of side-by-side dominoes). It is well-known that T(R) is connected when R is simply connected. By using graph theoretical approach, we show that the flip graph of 2m×(2n+1) quadriculated cylinder is still connected, but the flip graph of 2m×(2n+1) quadriculated torus is disconnected and consists of exactly two isomorphic components. For a tiling t, we associate an integer f(t), forcing number, as the minimum number of dominoes in t that is contained in no other tilings. As an application, 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.