Geodesic
Graph Exponentiation and Neighborhood Reconstruction
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 335-339

Voir la notice de l'article provenant de la source Library of Science

Any graph G admits a neighborhood multiset 𝒩(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 𝒩(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 G^K_2 ≅ H^K_2 ⇒ G ≅ H.
Keywords: neighborhood reconstructible graphs, graph exponentiation 
Hammack, Richard H. Graph Exponentiation and Neighborhood Reconstruction. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 335-339. http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a20/
@article{DMGT_2021_41_1_a20,
     author = {Hammack, Richard H.},
     title = {Graph {Exponentiation} and {Neighborhood} {Reconstruction}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {335--339},
     year = {2021},
     volume = {41},
     number = {1},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a20/}
}
TY  - JOUR
AU  - Hammack, Richard H.
TI  - Graph Exponentiation and Neighborhood Reconstruction
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 335
EP  - 339
VL  - 41
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a20/
LA  - en
ID  - DMGT_2021_41_1_a20
ER  - 
%0 Journal Article
%A Hammack, Richard H.
%T Graph Exponentiation and Neighborhood Reconstruction
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 335-339
%V 41
%N 1
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_1_a20/
%G en
%F DMGT_2021_41_1_a20

[1] M. Aigner and E. Triesch, Realizability and uniqueness in graphs, Discrete Math. 136 (1994) 3–20. doi: 10.1016/0012-365X(94)00104-Q

[2] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Second Edition, Series: Discrete Mathematics and its Applications (CRC Press, 2011).

[3] R. Hammack and C. Mullican, Neighborhood reconstruction and cancellation of graphs, Electron. J. Combin. 24 (2017) #P2.8

[4] B. Jónsson, Arithmetic of ordered sets, in: I. Rival (Ed.), Ordered Sets (Banff Alta, 1981), Volume 83 of NATO Advanced Study Inst. Ser. C. Math. Phys. Sci. 3–43.

[5] R. Mizzi, Two-Fold Isomorphisms, Ph.D. Dissertation (University of Malta, 2016).

[6] L. Lovász, Operations with structures, Acta Math. Acad. Sci. Hungar. 18 (1967) 321–328. doi: 10.1007/BF02280291

[7] L. Lovász, On the cancellation law among finite relational structures, Period. Math. Hungar. 1 (1971) 145–156. doi: 10.1007/BF02029172

[8] N. Sauer, Hedetniemi’s conjecture—a survey, Discrete Math. 229 (2001) 261–292. doi: 10.1016/S0012-365X(00)00213-2

[9] V.T. Sós, Problem, in: A. Hajnal and V.T. Sós, (Eds.), Combinatorics Coll. Math. Soc. J. Bolyai 18 (North-Holland, Amsterdam, 1978) 1214.