Successive vertex orderings of fully regular graphs

Fang, L. and Huang, H. and Pach, János and Tardos, Gábor and Zuo, J. (2023) Successive vertex orderings of fully regular graphs. JOURNAL OF COMBINATORIAL THEORY SERIES A, 199. ISSN 0097-3165

Preview

Text 1-s2.0-S0097316523000444-main.pdf Available under License Creative Commons Attribution Non-commercial No Derivatives. Download (352kB) | Preview

Abstract

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. © 2023 The Author(s)

Actions (login required)

Edit Item