Reconstruction of C_4-free graphs from the set of closed neighborhoods and digital convexity

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.