Realizations and Uniqueness of Cut Complexes of Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909962813308928 |
|---|---|
| author | Shen, Yufeng Song, Zhiyu Yu, Fenglin Zhou, Leopold Wuhan Zhuang, Jingqi |
| author_facet | Shen, Yufeng Song, Zhiyu Yu, Fenglin Zhou, Leopold Wuhan Zhuang, Jingqi |
| contents | In this paper, we investigate three fundamental problems regarding cut complexes of graphs: their realizability, the uniqueness of graph reconstruction from them, and their algorithmic recognition. We define the parameter $m(d,n)$ as the minimum number of additional vertices needed to realize any $d$-dimensional simplicial complex on $n$ vertices as a cut complex, and prove foundational bounds. Furthermore, we characterize precisely when a graph on $n \geq 5$ vertices is uniquely reconstructible from its $3$-cut complex. Based on this characterization, we develop an $O(n^4)$ recognition algorithm. These results deepen the connection between graph structure and the topology of cut complexes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_12933 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Realizations and Uniqueness of Cut Complexes of Graphs Shen, Yufeng Song, Zhiyu Yu, Fenglin Zhou, Leopold Wuhan Zhuang, Jingqi Combinatorics 05C69, 05E45, 05C85 In this paper, we investigate three fundamental problems regarding cut complexes of graphs: their realizability, the uniqueness of graph reconstruction from them, and their algorithmic recognition. We define the parameter $m(d,n)$ as the minimum number of additional vertices needed to realize any $d$-dimensional simplicial complex on $n$ vertices as a cut complex, and prove foundational bounds. Furthermore, we characterize precisely when a graph on $n \geq 5$ vertices is uniquely reconstructible from its $3$-cut complex. Based on this characterization, we develop an $O(n^4)$ recognition algorithm. These results deepen the connection between graph structure and the topology of cut complexes. |
| title | Realizations and Uniqueness of Cut Complexes of Graphs |
| topic | Combinatorics 05C69, 05E45, 05C85 |
| url | https://arxiv.org/abs/2512.12933 |