On Representable Graphs
On Representable Graphs
复制标题
DOI：
10.25596/jalc-2008-045
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
S. Kitaev;A. Pyatkin
中科院分区：
文献类型：
--
作者：
S. Kitaev;A. Pyatkin
图G = （V， E）是可表征的，当且仅当(x, y)∈E中每个x≠y时，在字母V上存在一个单词W，使得字母x和y在W中交替出现，如果W是k均匀的（W的每个字母在其中恰好出现k次），则G称为k可表征的。我们证明了一个图是可表征的当且仅当它在k点上是k可表征的。本文给出了一些不可表征图的例子。证明了一些广义的图是2-可表示和3-可表示的。提出了几个有待解决的问题。
A graph G = (V, E) is 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 for each x ≠ y. If W is k-uniform (each letter of W occurs exactly k times in it) then G is called k-representable. We prove that a graph is representable if and only if it is k-representable for some k. Examples of non-representable graphs are found in this paper. Some wide classes of graphs are proven to be 2- and 3-representable. Several open problems are stated.