### 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.

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.

Original language | English |
---|---|

Number of pages | 13 |

Journal | Graphs and Combinatorics |

Early online date | 30 Mar 2016 |

DOIs | |

Publication status | E-pub ahead of print - 30 Mar 2016 |

### Keywords

- word-representability
- semi-transitive orientation
- face subdivision
- triangular grid graphs
- Sierpinski gasket graph

## Fingerprint Dive into the research topics of 'Word-representability of face subdivisions of triangular grid graphs'. Together they form a unique fingerprint.

## Cite this

Chen, H. Z. Q., Kitaev, S., & Sun, B. Y. (2016). Word-representability of face subdivisions of triangular grid graphs.

*Graphs and Combinatorics*. https://doi.org/10.1007/s00373-016-1693-z