Graph Exponentiation and Neighborhood Reconstruction
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 neigh...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2021-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2186 |
| _version_ | 1797757781505212416 |
|---|---|
| author | Hammack Richard H. |
| author_facet | Hammack Richard H. |
| author_sort | Hammack Richard H. |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T18:19:31Z |
| format | Article |
| id | doaj.art-b6d41b99e517424ba394adbb9e7387da |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T18:19:31Z |
| publishDate | 2021-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-b6d41b99e517424ba394adbb9e7387da2023-08-02T08:59:12ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922021-02-0141133533910.7151/dmgt.2186dmgt.2186Graph Exponentiation and Neighborhood ReconstructionHammack Richard H.0Department of Mathematics and Applied Mathematics, Virginia Commonwealth University, Richmond, VA23284-2014, USAAny 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.https://doi.org/10.7151/dmgt.2186neighborhood reconstructible graphsgraph exponentiation05c6005c76 |
| spellingShingle | Hammack Richard H. Graph Exponentiation and Neighborhood Reconstruction Discussiones Mathematicae Graph Theory neighborhood reconstructible graphs graph exponentiation 05c60 05c76 |
| title | Graph Exponentiation and Neighborhood Reconstruction |
| title_full | Graph Exponentiation and Neighborhood Reconstruction |
| title_fullStr | Graph Exponentiation and Neighborhood Reconstruction |
| title_full_unstemmed | Graph Exponentiation and Neighborhood Reconstruction |
| title_short | Graph Exponentiation and Neighborhood Reconstruction |
| title_sort | graph exponentiation and neighborhood reconstruction |
| topic | neighborhood reconstructible graphs graph exponentiation 05c60 05c76 |
| url | https://doi.org/10.7151/dmgt.2186 |
| work_keys_str_mv | AT hammackrichardh graphexponentiationandneighborhoodreconstruction |