Word-representability of face subdivisions of triangular grid graphs

Herman Z.Q. Chen, Sergey Kitaev, Brian Y. Sun

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)
31 Downloads (Pure)

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.
Original languageEnglish
Number of pages13
JournalGraphs and Combinatorics
Early online date30 Mar 2016
DOIs
Publication statusE-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