Reconstructing trees from digitally convex sets

Suppose V is a finite set and C a collection of subsets of V that contains 0̸ and V and is closed under taking intersections. Then C is called a convexity and the ordered pair (V,C) is called an aligned space and the elements of C are referred to as convex sets. For a set S⊆V, the convex hull of S relative to C, denoted by CHC(S), is the smallest convex set containing S. A set S of vertices in a graph G with vertex set V is digitally convex if for every vertex v∈V, N[v]⊆N[S] implies v∈S. It is shown that every tree is uniquely determined by its digitally convex sets. These ideas can be used to show that every graph with girth at least 7 is uniquely determined by its digitally convex sets. Given the digitally convex sets of a graph it can be determined efficiently, as a function of the number of convex sets, if these are those of a tree.