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

• neighborhood reconstructible graphs
• graph exponentiation
• 05c60
• 05c76