Words and Graphs
Words and Graphs
复制标题
DOI：
10.1007/978-3-319-25859-1
复制
发表时间：
2016-08
期刊：
影响因子：
--
通讯作者：
S. Kitaev;V. Lozin
中科院分区：
文献类型：
--
作者：
S. Kitaev;V. Lozin
在1918年，海因茨普吕弗[120]发现了一个有趣的关系之间的标记树与n个顶点和序列的长度n− 2所构成的元素的集合{1，2，.，n}。这种关系实际上是一种双射，即树和序列之间的一一对应，它使普吕弗能够证明凯莱关于n顶点标记树的数量的公式。普吕弗序列是一个经典的例子，说明了词对于图枚举的重要性。更重要的是，随着计算机时代的到来，用文字表示图形对于在计算机内存中存储图形变得至关重要。文字也被用来揭示和描述各种有用的性质的图，如类，许多困难的算法问题变得容易，或类是良好的准有序的诱导子图关系。另一方面，图经常被用来研究词的各种性质和相关的组合结构，如排列。自从普吕弗序列被发现以来，词和图之间的相互作用在两个方向上都被反复研究。在这一领域的最新发现之一是词表示图的概念。这是几个研究得很好的图类的常见推广，例如圈图，可比图，3-列图和度最多为3的图（也称为次三次图）。文字表示图的发明成为本书写作的灵感来源。另一方面，它促使我们去研究单词和图形之间的其他各种重要关系。在本书的第一部分，我们报告，在一个全面的方式，艺术状态的词表示图，并给出了一个简短的游览相关的图形类。在第二部分中，我们探索了单词和图形之间的许多其他联系。我们对这些联系的描述决不是全面或完整的。相反，它是一个邀请，一个面临许多巨大挑战，并提供了许多伟大发现的前景的地区。
In 1918, Heinz Prüfer [120] discovered a fascinating relationship between labelled trees with n vertices and sequences of length n− 2 made of the elements of the set {1, 2,..., n}. This relationship is, in fact, a bijection, ie a one-to-one correspondence between trees and sequences, and it allowed Prüfer to prove Cayley’s formula about the number of n-vertex labelled trees. The Prüfer sequence is a classical example showing the importance of words for graph enumeration. More importantly, with the advent of the computer era representing graphs by words became crucial for storing graphs in computer memory. Words have also been used to reveal and describe various useful properties of graphs, such as classes where many difficult algorithmic problems become easy, or classes that are well-quasi-ordered by the induced subgraph relation. On the other hand, graphs have frequently been exploited to study various properties of words and related combinatorial structures, such as permutations.Since the discovery of the Prüfer sequence, the interplay between words and graphs has repeatedly been investigated in both directions. One of the most recent findings in this area is the notion of word-representable graphs. This is a common generalization of several well-studied classes of graphs, such as circle graphs, comparability graphs, 3-colourable graphs and graphs of degree at most 3 (also known as subcubic graphs). The invention of word-representable graphs became the inspiration for writing this book. On the other hand, it motivated us to look at various other important relationships between words and graphs. In the first part of the book, we report, in a comprehensive way, the state of the art on word-representable graphs and give a brief tour over related graph classes. In the second part, we explore many other connections between words and graphs. In no way is our description of these connections comprehensive or complete. Rather, it is an invitation to an area that faces many great challenges and offers the prospect of many great discoveries.