On 132-representable graphs

zbMATH Open1375.05181arXiv1602.08965MaRDI QIDQ4595641FDOQ4595641

Philip B. Zhang, Alice L. L. Gao, Sergey Kitaev

Publication date: 6 December 2017

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 $xy$ is an edge in $E$. Word-representable graphs are the subject of a long research line in the literature initiated in cite{KP}, and they are the main focus in the recently published book cite{KL}. A word $w=w_{1}cdots{w}_n$ avoids the pattern $132$ if there are no $1leq{i}_1<i_2<i_{3}leqn$ such that $w_{i_1}<w_{i_3}<w_{i_2}$. The theory of patterns in words and permutations is a fast growing area discussed in cite{HM,Kit}. A research direction suggested in cite{KL} is in merging the theories of word-representable graphs and patterns in words. Namely, given a class of pattern-avoiding words, can we describe the class of graphs represented by the words? Our paper provides the first non-trivial results in this direction. We say that a graph is 132-representable if it can be represented by a 132-avoiding word. We show that each 132-representable graph is necessarily a circle graph. Also, we show that any tree and any cycle graph are 132-representable, which is a rather surprising fact taking into account that most of these graphs are non-representable in the sense specified, as a generalization of the notion of a word-representable graph, in cite{JKPR}. Finally, we provide explicit 132-avoiding representations for all graphs on at most five vertices, and also describe all such representations, and enumerate them, for complete graphs.

Full work available at URL: https://arxiv.org/abs/1602.08965

Recommendations

• On graphs representable by pattern-avoiding words
• Representing graphs via pattern avoiding words
• Word-Representable Graphs: a Survey
• Enumeration and extensions of word-representants
• On representable graphs

zbMATH Keywords

word-representable graph

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Cited In (5)

• Forbidden pattern characterizations of 12-representable graphs defined by pattern-avoiding words
• Word-Representable Graphs: a Survey
• Wiener-type indices of Parikh word representable graphs
• Solving computational problems in the theory of word-representable graphs
• On graphs representable by pattern-avoiding words

This page was built for publication: On 132-representable graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4595641)