论文标题
完全常规图的连续顶点顺序
Successive vertex orderings of fully regular graphs
论文作者
论文摘要
图g =（v，e）如果对于每一个独立集$ i \ subset v $，则在$ v \ setminus $ i中的顶点的数量与I的任何元素无关，仅取决于I。完全常规图的顺序。 作为结果的应用，我们给出了Stanley和Gao + Peng的两个定理的替代证明，分别确定了完整图的线性边缘顺序数量和完整的两部分图，其中第一个I边缘诱导了连接的子库。作为另一个应用程序，我们为完整的3-优型超图的Hyperedges的线性订购数量提供了一个简单的产品公式，以便对于每个I，第一个I Hyperedges都会诱发连接的子图。我们发现了类似的公式，用于完整的（非目标）3-均匀的超图，并且在另一种密切相关的情况下，但是我们只有在顶点数量很少时才能对其进行验证。
A graph G = (V,E) is called fully regular if for every independent set $I\subset V$ , the number of vertices in $V\setminus$ I that are not connected to any element of I depends only on the size of I. A linear ordering of the vertices of G is called successive if for every i, the first i vertices induce a connected subgraph of G. We give an explicit formula for the number of successive vertex orderings of a fully regular graph. As an application of our results, we give alternative proofs of two theorems of Stanley and Gao + Peng, determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first i edges induce a connected subgraph. As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every i, the first i hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small.
