Reconstructing C4-free graphs from their digital convexity

MacKenzie Carr, Toronto Metropolitan University

Fomin, Kratochvíl, Lokshtanov, Mancini, and Telle showed that every C4-free graph is reconstructible from the multiset of closed neighborhoods. We strengthen their result proving that every C4-free graph is reconstructible from the set of closed neighborhoods. A subset S of vertices in a graph G is digitally convex if, for every v ̸∈ 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, thereby extending the work of Lafrance, Oellermann, and Pressey by showing that all C4-free graphs, and hence all graphs of girth at least five, are reconstructible from their digitally convex sets.