Boundary Properties of Factorial Classes of Graphs
Boundary Properties of Factorial Classes of Graphs
复制标题
图阶乘类的边界性质
作者：
V. Lozin;V. Zamaraev
对于一类图形x，让xn为X类中带顶点集{1，…，n}的图数，也称为X的速度。在诱发子图下封闭的速度一致性离散层和前四个层是恒定的，多项式，指数和阶乘的阶段。这些信息允许对前三个的全局结构表征，而这些层是一个段落的阶段。没有这样的阶级，并且可能存在这样的阶级。研究算法图问题并揭示阶乘层的前几个边界类。
For a class of graphs X, let Xn be the number of graphs with vertex set {1,…,n} in the class X, also known as the speed of X. It is known that in the family of hereditary classes (i.e. those that are closed under taking induced subgraphs) the speeds constitute discrete layers and the first four lower layers are constant, polynomial, exponential, and factorial. For each of these four layers a complete list of minimal classes is available, and this information allows to provide a global structural characterization for the first three of them. The minimal layer for which no such characterization is known is the factorial one. A possible approach to obtaining such a characterization could be through identifying all minimal superfactorial classes. However, no such class is known and possibly no such class exists. To overcome this difficulty, we employ the notion of boundary classes that has been recently introduced to study algorithmic graph problems and reveal the first few boundary classes for the factorial layer.