Word-representability of face subdivisions of triangular grid graphs

Chen, Herman Z.Q. and Kitaev, Sergey and Sun, Brian Y. (2016) Word-representability of face subdivisions of triangular grid graphs. Graphs and Combinatorics. ISSN 0911-0119 (https://doi.org/10.1007/s00373-016-1693-z)

[thumbnail of Chen-Kitaev-Sun-GC2016-word-representability-of-face-subdivisions-of-triangular-grid-graphs]
Preview
 Text. Filename: Chen_Kitaev_Sun_GC2016_word_representability_of_face_subdivisions_of_triangular_grid_graphs.pdf
Accepted Author Manuscript
Download (260kB)| Preview

Abstract

A graph G = (V, E) 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 (x, y) ∈ E. 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 K4. Inspired by a recent elegant result of Akrobotu et al., who classified wordrepresentable 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 Sierpi´nski gasket graph is wordrepresentable.

ORCID iDs

Chen, Herman Z.Q., Kitaev, Sergey ORCID logoORCID: https://orcid.org/0000-0003-3324-1647 and Sun, Brian Y.;
CORE (COnnecting REpositories)