Neighborhood reconstruction and cancellation of graphs (Q528982)

Summary: We connect two seemingly unrelated problems in graph theory. { }Any graph \(G\) has a neighborhood multiset \(\mathscr{N}(G)= \{N(x) \mid x\in V(G)\}\) whose elements are precisely the open vertex-neighborhoods of \(G\). In general there exist non-isomorphic graphs \(G\) and \(H\) for which \(\mathscr{N}(G)=\mathscr{N}(H)\). The neighborhood reconstruction problem asks the conditions under which \(G\) is uniquely reconstructible from its neighborhood multiset, that is, the conditions under which \(\mathscr{N}(G)=\mathscr{N}(H)\) implies \(G\cong H\). Such a graph is said to be neighborhood-reconstructible. { }The cancellation problem for the direct product of graphs seeks the conditions under which \(G\times K\cong H\times K\) implies \(G\cong H\). \textit{L. Lovász} [Period. Math. Hung. 1, 145--156 (1971; Zbl 0223.08002)] proved that this is indeed the case if \(K\) is not bipartite. A second instance of the cancellation problem asks for conditions on \(G\) that assure \(G\times K\cong H\times K\) implies \(G\cong H\) for any bipartite \(K\) with \(E(K)\neq \emptyset\). A graph \(G\) for which this is true is called a cancellation graph. { }We prove that the neighborhood-reconstructible graphs are precisely the cancellation graphs. We also present some new results on cancellation graphs, which have corresponding implications for neighborhood reconstruction. We are particularly interested in the (yet-unsolved) problem of finding a simple structural characterization of cancellation graphs (equivalently, neighborhood-reconstructible graphs).