Implicit representations and factorial properties of graphs
Implicit representations and factorial properties of graphs
复制标题
图的隐式表示和阶乘属性
DOI：
10.1016/j.disc.2014.09.008
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
Atminas A
中科院分区：
文献类型：
--
作者：
Atminas A
图的隐式表示的思想是在Kannan et al.（1992），可以定义如下。一个n-顶点图G的表示称为隐式表示，如果它给G的每个顶点分配一个长度为O（log n）的二进制码，使得两个顶点的邻接是它们的码的函数。由于一个n-顶点图的隐式表示使用O（n log n）位，任何一类允许这种表示的图包含2个O（n log n）标记的n个顶点的图。在Balogh et al.（2000）这样的类最多有阶乘增长速度。在这个术语中，隐图猜想可以表述如下：每一个具有最多阶乘增长速度的遗传类都有一个隐式表示。决定一个给定的遗传类是否至多具有阶乘的增长速度，这个问题远不是一个微不足道的问题。在本文中，我们介绍了一些工具，简化了这个问题。其中一些可以用来获得一个更强的结论存在的隐式表示。我们应用我们的工具来揭示新的遗传类的阶乘增长速度。对于他们中的许多人，我们表明存在一个隐式表示。
The idea of implicit representation of graphs was introduced in Kannan et al.(1992) and can be defined as follows. A representation of an n-vertex graph G is said to be implicit if it assigns to each vertex of G a binary code of length O (log n) so that the adjacency of two vertices is a function of their codes. Since an implicit representation of an n-vertex graph uses O (n log n) bits, any class of graphs admitting such a representation contains 2 O (n log n) labelled graphs with n vertices. In the terminology of Balogh et al.(2000) such classes have at most factorial speed of growth. In this terminology, the implicit graph conjecture can be stated as follows: every class with at most factorial speed of growth which is hereditary admits an implicit representation. The question of deciding whether a given hereditary class has at most factorial speed of growth is far from being trivial. In the present paper, we introduce a number of tools simplifying this question. Some of them can be used to obtain a stronger conclusion on the existence of an implicit representation. We apply our tools to reveal new hereditary classes with the factorial speed of growth. For many of them we show the existence of an implicit representation.
登录
查看更多内容
无伽玛矩阵中的非冗余 1
影响因子：
0.8
作者：
J. Spinrad
通讯作者：
J. Spinrad
影响因子：
0.9
作者：
Peter Allen
通讯作者：
Peter Allen
派系宽度和遗传特性的速度
影响因子：
0.7
作者：
Peter Allen;V. Lozin;M. Rao
通讯作者：
M. Rao
影响因子：
0.9
作者：
V. Lozin;V. Zamaraev
通讯作者：
V. Zamaraev
DOI：
--
发表时间：
2012
期刊：
European journal of combinatorics (Print)
影响因子：
--
作者：
V. Lozin;Colin Mayhill;V. Zamaraev
通讯作者：
V. Zamaraev