DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

R. Hammack

Title:

Graph exponentiation and neighborhood reconstruction

Source:

Discussiones Mathematicae Graph Theory

Received: 2018-09-03, Revised: 2018-09-03, Accepted: 2018-10-27, https://doi.org/10.7151/dmgt.2186

Abstract:

Any graph $G$ admits a neighborhood multiset $\mathscr{N}(G)= \{N_G(x) | x\in 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^{K_2}\cong H^{K_2} \Longrightarrow G\cong H$.

Keywords:

neighborhood reconstructible graphs, graph exponentiation

PDF
Close