Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity
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_ | 1866917039336062976 |
|---|---|
| author | Borgwardt, Steffen Carr, MacKenzie Chen, Ce Ge, Wayne Hartke, Stephen G. Huang, Yixuan Moon, Alex |
| author_facet | Borgwardt, Steffen Carr, MacKenzie Chen, Ce Ge, Wayne Hartke, Stephen G. Huang, Yixuan Moon, Alex |
| contents | Fomin, Kratochvíl, Lokshtanov, Mancini, and Telle showed that every $C_{4}$-free graph is reconstructible from the \emph{multiset} of closed neighborhoods. We strengthen their result proving that every $C_{4}$-free graph is reconstructible from the \emph{set} of closed neighborhoods.
This extends the work of Lafrance et al.\ by showing that all $C_{4}$-free graphs, and hence all graphs of girth at least five, are reconstructible from their digitally convex sets.
A subset $S$ of vertices in a graph $G$ is digitally convex if, for every vertex $v \notin S$, there is a private neighbor of $v$.
We establish that reconstruction from digitally convex sets is equivalent to reconstruction from the set of closed neighborhoods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_21195 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity Borgwardt, Steffen Carr, MacKenzie Chen, Ce Ge, Wayne Hartke, Stephen G. Huang, Yixuan Moon, Alex Combinatorics 05C60, 05C75 Fomin, Kratochvíl, Lokshtanov, Mancini, and Telle showed that every $C_{4}$-free graph is reconstructible from the \emph{multiset} of closed neighborhoods. We strengthen their result proving that every $C_{4}$-free graph is reconstructible from the \emph{set} of closed neighborhoods. This extends the work of Lafrance et al.\ by showing that all $C_{4}$-free graphs, and hence all graphs of girth at least five, are reconstructible from their digitally convex sets. A subset $S$ of vertices in a graph $G$ is digitally convex if, for every vertex $v \notin S$, there is a private neighbor of $v$. We establish that reconstruction from digitally convex sets is equivalent to reconstruction from the set of closed neighborhoods. |
| title | Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity |
| topic | Combinatorics 05C60, 05C75 |
| url | https://arxiv.org/abs/2510.21195 |