Picture of smart phone in human hand

World leading smartphone and mobile technology 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 Strathclyde researchers from the Department of Computer & Information Sciences involved in researching exciting new applications for mobile and smartphone technology. But the transformative application of mobile technologies is also the focus of research within disciplines as diverse as Electronic & Electrical Engineering, Marketing, Human Resource Management and Biomedical Enginering, among others.

Explore Strathclyde's Open Access research on smartphone technology now...

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

[img]
Preview
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

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.