Word-Representability of Face Subdivisions of Triangular Grid Graphs

摘要

A graph is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w if and only if . A triangular grid graph is a subgraph of a tiling of the plane with equilateral triangles defined by a finite number of triangles, called cells. A face subdivision of a triangular grid graph is replacing some of its cells by plane copies of the complete graph . Inspired by a recent elegant result of Akrobotu et al., who classified word-representable triangulations of grid graphs related to convex polyominoes, we characterize word-representable face subdivisions of triangular grid graphs. A key role in the characterization is played by smart orientations introduced by us in this paper. As a corollary to our main result, we obtain that any face subdivision of boundary triangles in the SierpiA"ski gasket graph is word-representable.