Discussiones Mathematicae Graph Theory (Feb 2021)
Graph Exponentiation and Neighborhood Reconstruction
Abstract
Any graph G admits a neighborhood multiset π©(G) = {NG(x) | x β V (G)} whose elements are precisely the open neighborhoods of G. We say G is neighborhood reconstructible if it can be reconstructed from π©(G), that is, if G β H whenever π© (G) = π©(H) for some other graph H. This note characterizes neighborhood reconstructible graphs as those graphs G that obey the exponential cancellation GK2 β HK2 β G β = H.
Keywords