





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。