{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:43:56Z","timestamp":1753893836859,"version":"3.41.2"},"reference-count":0,"publisher":"The Electronic Journal of Combinatorics","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Electron. J. Combin."],"abstract":"<jats:p>We connect two seemingly unrelated problems in graph theory.Any graph $G$ has a neighborhood multiset $\\mathscr{N}(G)= \\{N(x) \\mid x\\in V(G)\\}$\u00a0whose elements are precisely the open vertex-neighborhoods of $G$. In general there exist non-isomorphic graphs\u00a0$G$ and $H$ for which $\\mathscr{N}(G)=\\mathscr{N}(H)$. The neighborhood reconstruction problem\u00a0asks the conditions under which $G$ is uniquely reconstructible from its neighborhood multiset, that is,\u00a0the conditions under which $\\mathscr{N}(G)=\\mathscr{N}(H)$ implies $G\\cong H$. Such a graph is said to be neighborhood-reconstructible.The cancellation problem for the direct product of graphs seeks the conditions under which\u00a0$G\\times K\\cong H\\times K$ implies $G\\cong H$. Lov\u00e1sz proved that this is indeed the case if $K$ is not bipartite.\u00a0A second instance of the cancellation problem asks for\u00a0conditions on $G$ that assure $G\\times K\\cong H\\times K$ implies $G\\cong H$ for any bipartite~$K$ with $E(K)\\neq \\emptyset$.\u00a0A graph $G$ for which this is true is called a cancellation graph.We prove that the neighborhood-reconstructible graphs\u00a0are precisely the cancellation graphs.\u00a0We also present some new results on cancellation graphs, which have\u00a0corresponding implications for neighborhood reconstruction.\u00a0We are particularly interested in the (yet-unsolved) problem of\u00a0finding a simple structural characterization of cancellation graphs\u00a0(equivalently, neighborhood-reconstructible graphs).<\/jats:p>","DOI":"10.37236\/6676","type":"journal-article","created":{"date-parts":[[2020,1,10]],"date-time":"2020-01-10T15:55:54Z","timestamp":1578671754000},"source":"Crossref","is-referenced-by-count":0,"title":["Neighborhood Reconstruction and Cancellation of Graphs"],"prefix":"10.37236","volume":"24","author":[{"given":"Richard H.","family":"Hammack","sequence":"first","affiliation":[]},{"given":"Cristina","family":"Mullican","sequence":"additional","affiliation":[]}],"member":"23455","published-online":{"date-parts":[[2017,4,13]]},"container-title":["The Electronic Journal of Combinatorics"],"original-title":[],"link":[{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p8\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/download\/v24i2p8\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,17]],"date-time":"2020-01-17T05:02:15Z","timestamp":1579237335000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v24i2p8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,13]]},"references-count":0,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2017,4,13]]}},"URL":"https:\/\/doi.org\/10.37236\/6676","relation":{},"ISSN":["1077-8926"],"issn-type":[{"type":"electronic","value":"1077-8926"}],"subject":[],"published":{"date-parts":[[2017,4,13]]},"article-number":"P2.8"}}