Word-Representability of Face Subdivisions of Triangular Grid Graphs

详细信息    查看全文

• 作者：Herman Z. Q. Chen ; Sergey Kitaev ; Brian Y. Sun
• 关键词：Word ; representability ; Semi ; transitive orientation ; Face subdivision ; Triangular grid graphs ; Sierpiński gasket graph
• 刊名：Graphs and Combinatorics
• 出版年：2016
• 出版时间：September 2016
• 年：2016
• 卷：32
• 期：5
• 页码：1749-1761
• 全文大小：887 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Combinatorics
  Engineering Design
  
• 出版者：Springer Japan
• ISSN：1435-5914
• 卷排序：32

文摘

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)\in 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 \(K_4\). Inspired by a recent elegant result of Akrobotu et al., who classified word-representable 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ński gasket graph is word-representable.