2023/10/05 by Boon Suan Ho, Ho, Boon Suan
Computer Science · Mathematics · #05A19 (Primary) 05C30 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2310.03356
openalex publication_date 2023/10/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A vertex ordering of a graph G is a bijection π\colon\1,…,|V(G)|\→ V(G). It is successive if the induced subgraph G[vπ(1),…,vπ(k)] is connected for each k. Lixing Fang, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo [J. Comb. Theory A199 (2023), 105776] gave formulas for counting the number of successive vertex orderings for a class of graphs they called "fully regular," and conjectured that these formulas could be written as certain products involving differences or ratios of binomial coefficients in two cases: When the graph is the line graph L(Kn(3)) of the complete 3-uniform hypergraph, or when it is the line graph L(Km,n(1,2)) of a complete "bipartite" 3-uniform hypergraph. In this paper, we confirm both of these conjectures.