Authors:
R. Hammack
Title:
Graph exponentiation and neighborhood reconstruction
Source:
Discussiones Mathematicae Graph Theory
Received 03.09.2018, Revised 03.09.2018, Accepted 27.10.2018, doi: 10.7151/dmgt.2186

Abstract:
Any graph G admits a neighborhood multiset \mathscr{N}(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 \mathscr{N}(G), that is, if G\cong H whenever \mathscr{N}(G)=\mathscr{N}(H) for some other graph H. This note characterizes neighborhood reconstructible graphs as those graphs G that obey the exponential cancellation GK2\cong HK2 \Longrightarrow G\cong H.
Keywords:
neighborhood reconstructible graphs, graph exponentiation

Links:
PDF