Successive vertex orderings of fully regular graphs
Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.
Download
Journal Article
| Published
| English
Scopus indexed
Author
Fang, Lixing;
Huang, Hao;
Pach, JánosISTA;
Tardos, Gábor;
Zuo, Junchi
Department
Abstract
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.
Publishing Year
Date Published
2023-10-01
Journal Title
Journal of Combinatorial Theory. Series A
Volume
199
Issue
10
Article Number
105776
ISSN
eISSN
IST-REx-ID
Cite this
Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully regular graphs. Journal of Combinatorial Theory Series A. 2023;199(10). doi:10.1016/j.jcta.2023.105776
Fang, L., Huang, H., Pach, J., Tardos, G., & Zuo, J. (2023). Successive vertex orderings of fully regular graphs. Journal of Combinatorial Theory. Series A. Elsevier. https://doi.org/10.1016/j.jcta.2023.105776
Fang, Lixing, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo. “Successive Vertex Orderings of Fully Regular Graphs.” Journal of Combinatorial Theory. Series A. Elsevier, 2023. https://doi.org/10.1016/j.jcta.2023.105776.
L. Fang, H. Huang, J. Pach, G. Tardos, and J. Zuo, “Successive vertex orderings of fully regular graphs,” Journal of Combinatorial Theory. Series A, vol. 199, no. 10. Elsevier, 2023.
Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.
Fang, Lixing, et al. “Successive Vertex Orderings of Fully Regular Graphs.” Journal of Combinatorial Theory. Series A, vol. 199, no. 10, 105776, Elsevier, 2023, doi:10.1016/j.jcta.2023.105776.
All files available under the following license(s):
Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0):
Main File(s)
File Name
2023_JourCombinatiorialTheory_Fang.pdf
352.56 KB
Access Level
Open Access
Date Uploaded
2024-01-30
MD5 Checksum
9eebc213b4182a66063a99083ff5bd04
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2206.13592