Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity
Authors
Steffen Borgwardt
MacKenzie Carr
Ce Chen
Wayne Ge
Stephen G. Hartke
Yixuan Huang
Alex Moon
Abstract
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.
