Word-representability of line graphs
Word-representability of line graphs
复制标题
折线图的文字表示能力
DOI：
10.4236/ojdm.2011.12012
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Henning Úlfarsson
中科院分区：
文献类型：
--
作者：
S. Kitaev;P. Salimov;Christopher Severs;Henning Úlfarsson
一个图G=（V，E）是可表示的，如果在字母表V上存在一个词W，使得字母x和y在W中交替，当且仅当对于每个x不等于y，（x，y）在E中。研究可表示图的动机来自代数，但从图论，计算机科学和组合学的角度来看，这个主题很有趣。本文证明了当n大于3时，n轮的线图是不可表示的。这不仅提供了一种新的不可表示图的构造方法，而且回答了一个关于5轮线图--最小不可表示图的可表示性的公开问题。此外，我们证明了当n大于4时，完全图的线图也是不可表示的。然后，我们使用这些事实证明，给定一个图G，这是不是一个循环，一条道路或爪图，通过采取G的线图k次得到的图是保证是不可表示的k大于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) is in E for each x not equal to y . The motivation to study representable graphs came from algebra, but this subject is interesting from graph theoretical, computer science, and combinatorics on words points of view. In this paper, we prove that for n greater than 3, the line graph of an n-wheel is non-representable. This not only provides a new construction of non-repre- sentable graphs, but also answers an open question on representability of the line graph of the 5-wheel, the minimal non-representable graph. Moreover, we show that for n greater than 4, the line graph of the complete graph is also non-representable. We then use these facts to prove that given a graph G which is not a cycle, a path or a claw graph, the graph obtained by taking the line graph of G k-times is guaranteed to be non-representable for k greater than 3.