Successive vertex orderings of fully regular graphs
Fang, Lixing
Huang, Hao
Pach, János
Tardos, Gábor
Zuo, Junchi
ddc:510
A graph G=(V, E) is called fully regular if for every independent set I c 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.
Elsevier
2023
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/13165
https://research-explorer.ista.ac.at/download/13165/14902
Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory Series A</i>. 2023;199(10). doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jcta.2023.105776
info:eu-repo/semantics/altIdentifier/issn/0097-3165
info:eu-repo/semantics/altIdentifier/issn/1096-0899
info:eu-repo/semantics/altIdentifier/arxiv/2206.13592
https://creativecommons.org/licenses/by-nc-sa/4.0/
info:eu-repo/semantics/openAccess