{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:46:31Z","timestamp":1759063591407},"reference-count":5,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T00:00:00Z","timestamp":1221177600000},"content-version":"unspecified","delay-in-days":5582,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:p>Associate to a finite labeled graph <jats:italic>G<\/jats:italic>(<jats:italic>V, E<\/jats:italic>) its multiset of neighborhoods <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535xs1D4A9\" \/>(<jats:italic>G<\/jats:italic>) = {N(\u03c5): \u03c5 \u2208 <jats:italic>V<\/jats:italic>}. We discuss the question of when a list <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535xs1D4A9\" \/> is realizable by a graph, and to what extent <jats:italic>G<\/jats:italic> is determined by <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535xs1D4A9\" \/>(<jats:italic>G<\/jats:italic>). The main results are: the decision problem <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535inline1\" \/> is NP-complete; for bipartite graphs the decision problem is polynomially equivalent to Graph Isomorphism; forests <jats:italic>G<\/jats:italic> are determined up to isomorphism by <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535xs1D4A9\" \/>(<jats:italic>G<\/jats:italic>); and if <jats:italic>G<\/jats:italic> is connected bipartite and <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535xs1D4A9\" \/>(<jats:italic>H<\/jats:italic>) = <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" mimetype=\"image\" xlink:type=\"simple\" xlink:href=\"S0963548300000535xs1D4A9\" \/>(<jats:italic>G<\/jats:italic>), then <jats:italic>H<\/jats:italic> is completely described.<\/jats:p>","DOI":"10.1017\/s0963548300000535","type":"journal-article","created":{"date-parts":[[2008,9,12]],"date-time":"2008-09-12T11:19:08Z","timestamp":1221218348000},"page":"103-113","source":"Crossref","is-referenced-by-count":11,"title":["Reconstructing a Graph from its Neighborhood Lists"],"prefix":"10.1017","volume":"2","author":[{"given":"Martin","family":"Aigner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eberhard","family":"Triesch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2008,9,12]]},"reference":[{"key":"S0963548300000535_ref004","doi-asserted-by":"publisher","DOI":"10.1137\/0210002"},{"key":"S0963548300000535_ref003","volume-title":"Coll. Math. Soc. J. Bolyai","volume":"18","author":"Hajnal","year":"1978"},{"key":"S0963548300000535_ref002","first-page":"439","volume-title":"Graph Theory, Combinatorics and Applications","author":"Erd\u0151s","year":"1991"},{"key":"S0963548300000535_ref001","first-page":"264","article-title":"Graphs with prescribed degrees of vertices (Hungarian)","volume":"11","author":"Erd\u0151s","year":"1960","journal-title":"Math. Lapok"},{"key":"S0963548300000535_ref005","volume-title":"Progress in Theoretical Computer Science","author":"K\u00f6bler","year":"1993"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548300000535","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,15]],"date-time":"2019-05-15T22:49:08Z","timestamp":1557960548000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548300000535\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":5,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1993,6]]}},"alternative-id":["S0963548300000535"],"URL":"https:\/\/doi.org\/10.1017\/s0963548300000535","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}