Picture of person typing on laptop with programming code visible on the laptop screen

World class computing and information science research at Strathclyde...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of Open Access research papers by University of Strathclyde researchers, including by researchers from the Department of Computer & Information Sciences involved in mathematically structured programming, similarity and metric search, computer security, software systems, combinatronics and digital health.

The Department also includes the iSchool Research Group, which performs leading research into socio-technical phenomena and topics such as information retrieval and information seeking behaviour.


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

Text (Chen-Kitaev-Sun-GC2016-word-representability-of-face-subdivisions-of-triangular-grid-graphs)
Chen_Kitaev_Sun_GC2016_word_representability_of_face_subdivisions_of_triangular_grid_graphs.pdf - Accepted Author Manuscript

Download (260kB) | Preview


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.