### Abstract

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 |

### Fingerprint

### Keywords

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

### Cite this

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

}

**Word-representability of face subdivisions of triangular grid graphs.** / Chen, Herman Z.Q.; Kitaev, Sergey; Sun, Brian Y.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Word-representability of face subdivisions of triangular grid graphs

AU - Chen, Herman Z.Q.

AU - Kitaev, Sergey

AU - Sun, Brian Y.

N1 - The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-016-1693-z

PY - 2016/3/30

Y1 - 2016/3/30

N2 - A graph G = (V, E) is word-representable if there exists a wordw over the alphabet V such that letters x and y alternate in w if and onlyif (x, y) ∈ E. A triangular grid graph is a subgraph of a tiling of the planewith 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 byplane 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 introducedby us in this paper. As a corollary to our main result, we obtain that anyface subdivision of boundary triangles in the Sierpi´nski gasket graph is wordrepresentable.

AB - A graph G = (V, E) is word-representable if there exists a wordw over the alphabet V such that letters x and y alternate in w if and onlyif (x, y) ∈ E. A triangular grid graph is a subgraph of a tiling of the planewith 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 byplane 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 introducedby us in this paper. As a corollary to our main result, we obtain that anyface subdivision of boundary triangles in the Sierpi´nski gasket graph is wordrepresentable.

KW - word-representability

KW - semi-transitive orientation

KW - face subdivision

KW - triangular grid graphs

KW - Sierpinski gasket graph

UR - http://www.scopus.com/inward/record.url?scp=84962240385&partnerID=8YFLogxK

U2 - 10.1007/s00373-016-1693-z

DO - 10.1007/s00373-016-1693-z

M3 - Article

JO - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

ER -