Word-representability of face subdivisions of triangular grid graphs

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

Research output: Contribution to journalArticle

3 Citations (Scopus)

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.
LanguageEnglish
Number of pages13
JournalGraphs and Combinatorics
Early online date30 Mar 2016
DOIs
Publication statusE-pub ahead of print - 30 Mar 2016

Fingerprint

Grid Graph
Triangular Grid
Representability
Triangulation
Subdivision
Face
Triangle
Polyominoes
Equilateral triangle
Cell
Graph in graph theory
Tiling
Complete Graph
Alternate
Subgraph
Corollary

Keywords

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

Cite this

@article{c2e3572b27ee41bd8d7498d1e6b7ecf7,
title = "Word-representability of face subdivisions of triangular grid graphs",
abstract = "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.",
keywords = "word-representability, semi-transitive orientation, face subdivision, triangular grid graphs, Sierpinski gasket graph",
author = "Chen, {Herman Z.Q.} and Sergey Kitaev and Sun, {Brian Y.}",
note = "The final publication is available at Springer via http://dx.doi.org/10.1007/s00373-016-1693-z",
year = "2016",
month = "3",
day = "30",
doi = "10.1007/s00373-016-1693-z",
language = "English",
journal = "Graphs and Combinatorics",
issn = "0911-0119",

}

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

In: Graphs and Combinatorics, 30.03.2016.

Research output: Contribution to journalArticle

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

T2 - Graphs and Combinatorics

JF - Graphs and Combinatorics

SN - 0911-0119

ER -