Components of domino tilings under flips in quadriculated cylinder and torus

MaRDI QIDQ6417846zbMATH OpenFDO

Authors Qian-qian Liu, Jingfeng Wang, Chunmei Li, Heping Zhang

Publication date 20 November 2022

Abstract: 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 $mathcalT(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^{circ}$ rotation of a pair of side-by-side dominoes). It is well-known that $mathcalT(R)$ is connected when $R$ is simply connected. By using graph theoretical approach, we show that the flip graph of $2mimes(2n+1)$ quadriculated cylinder is still connected, but the flip graph of $2mimes(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 $2mimes(2n+1)$ quadriculated cylinder and torus form respectively an integer interval whose maximum value is $(n+1)m$.

This page was built for publication: Components of domino tilings under flips in quadriculated cylinder and torus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6417846)