Picture of athlete cycling

Open Access research with a real impact on health...

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 Strathclyde researchers, including by researchers from the Physical Activity for Health Group based within the School of Psychological Sciences & Health. Research here seeks to better understand how and why physical activity improves health, gain a better understanding of the amount, intensity, and type of physical activity needed for health benefits, and evaluate the effect of interventions to promote physical activity.

Explore open research content by Physical Activity for Health...

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.