2022/06/27 by Lixing Fang, Fang, Lixing, Hao Huang +7
Computer Science · Engineering · Mathematics · #05A15 #05C30 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Finite Group Theory Research #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2206.13592
openalex publication_date 2022/06/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G = (V,E) is called fully regular if for every independent set I⊂ V , the number of vertices in V∖ 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.