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)= {N_{G}(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 G^{K2}\cong H^{K2} \Longrightarrow G\cong H. | |
Keywords: neighborhood reconstructible graphs, graph exponentiation | |
Links: |