On 132-representable graphs
On 132-representable graphs
复制标题
在 132 个可表示的图上
DOI：
--
复制
发表时间：
2016-02
期刊：
影响因子：
--
通讯作者：
张彪
中科院分区：
文献类型：
--
作者：
郜璐璐;Sergey Kitaev;张彪
图$G=(V，E)$是单词可表示的，如果在字母表$V$上存在单词$w$，使得字母$x$和$y$交替出现在$w$中当且仅当$xy$是$E$中的一条边时。词可表示图是从Cite{KP}开始的文献中的一长串研究主题，也是最近出版的书{Cite{KL}中的主要焦点。如果没有$1\leq i_1<；i_2<；i_3\leq n$使得$w_{i_1}<；w_{i_3}<；w_{i_2}$，则单词$w=w_1\cdots w_{n}$可避免模式$132$。单词和排列中的模式理论是一个快速发展的领域，在Cite{HM，Kit}中讨论。
Cite{KL}提出的一个研究方向是将词表示的图形和词中的模式的理论融合在一起。也就是说，给定一类避免模式的词，我们能描述由这些词表示的图的类吗？我们的论文在这个方向上提供了第一个非平凡的结果。我们说一个图是132可表示的，如果它可以用一个避免132的词来表示。我们证明了每个132-可表示图必然是圈图。此外，我们证明了任何树和任何圈图都是132-可表示的，这是一个相当令人惊讶的事实，因为这些图中的大多数都是在指定的意义上不可表示的，作为词可表示图的概念的推广，在引用{JKPR}中。最后，我们给出了至多5个顶点上的所有图的显式132-避免表示，并对完全图的所有这样的表示进行了描述和列举。
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 $1\leq i_1<i_2<i_3\leq n$ 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.
登录
查看更多内容
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
M. Halldorsson;S. Kitaev
通讯作者：
M. Halldorsson;S. Kitaev
DOI：
10.37236/4946
发表时间：
2014-12
期刊：
Electron. J. Comb.
影响因子：
--
作者：
M. Jones;S. Kitaev;A. Pyatkin;J. Remmel
通讯作者：
M. Jones;S. Kitaev;A. Pyatkin;J. Remmel
DOI：
10.1007/978-3-319-25859-1
发表时间：
2016-08
期刊：
--
影响因子：
--
作者：
S. Kitaev;V. Lozin
通讯作者：
S. Kitaev;V. Lozin
DOI：
10.25596/jalc-2008-045
发表时间：
2008
期刊：
J. Autom. Lang. Comb.
影响因子：
--
作者：
S. Kitaev;A. Pyatkin
通讯作者：
S. Kitaev;A. Pyatkin
DOI：
10.1016/j.dam.2015.07.033
发表时间：
2015-01
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
M. Halldórsson;S. Kitaev;A. Pyatkin
通讯作者：
M. Halldórsson;S. Kitaev;A. Pyatkin