{"entities":{"Q528982":{"pageid":530749,"ns":120,"title":"Item:Q528982","lastrevid":62515929,"modified":"2026-04-11T06:36:47Z","type":"item","id":"Q528982","labels":{"en":{"language":"en","value":"Neighborhood reconstruction and cancellation of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6719978"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$D637B377-CDD7-43A1-AA69-FE6115E64AD9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0e552d5c6a29bafffb5f6f5a683bce6046372471","datavalue":{"value":{"text":"Neighborhood reconstruction and cancellation of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q528982$CBB4216D-2C73-4138-A53E-D0948C22B86B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"470dd35c3323ba4b4dcb67029d0d61e72bee2b29","datavalue":{"value":"1361.05111","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528982$EA8943FA-EB9B-45D3-AEF5-B06C3509D84C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"74f149bfd50ac9c5b3b1223e66127e32f9de966b","datavalue":{"value":{"entity-type":"item","numeric-id":340606,"id":"Q340606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$E299D596-5DAA-4955-882F-9CD934B22798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4392396e313eeb85f19a1c70faa064378460a72","datavalue":{"value":{"entity-type":"item","numeric-id":528981,"id":"Q528981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$F0109AFF-A3EB-4121-BB25-8E2507459361","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$B5B610C7-5FC8-4532-9157-3D0D4EE59DF6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"46a30028c10f94c4944c801c86f2de5dd37da0f3","datavalue":{"value":{"time":"+2017-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q528982$A35D7976-BFC0-4287-83D4-4274B836ED0A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d32e1f134dd85efff027e7573bcfd89cd83f2fa2","datavalue":{"value":"https://arxiv.org/abs/1612.02717","type":"string"},"datatype":"url"},"type":"statement","id":"Q528982$48503ACB-F001-4A59-AFEF-335FD28FCD82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"d63a080893110cb316aeaea092f764b0fc8696e9","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p8","type":"string"},"datatype":"url"},"type":"statement","id":"Q528982$DD03B82D-2DFD-49AB-8792-B947AD7B23B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"64adea965be7c91ac316df59a592de3f79019990","datavalue":{"value":"Summary: 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)\\}\\) whose elements are precisely the open vertex-neighborhoods of \\(G\\). In general there exist non-isomorphic graphs \\(G\\) and \\(H\\) for which \\(\\mathscr{N}(G)=\\mathscr{N}(H)\\). The neighborhood reconstruction problem asks the conditions under which \\(G\\) is uniquely reconstructible from its neighborhood multiset, that is, the 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 \\(G\\times K\\cong H\\times K\\) implies \\(G\\cong H\\). \\textit{L. Lov\u00e1sz} [Period. Math. Hung. 1, 145--156 (1971; Zbl 0223.08002)] proved that this is indeed the case if \\(K\\) is not bipartite. A second instance of the cancellation problem asks for conditions on \\(G\\) that assure \\(G\\times K\\cong H\\times K\\) implies \\(G\\cong H\\) for any bipartite \\(K\\) with \\(E(K)\\neq \\emptyset\\). A graph \\(G\\) for which this is true is called a cancellation graph. {  }We prove that the neighborhood-reconstructible graphs are precisely the cancellation graphs. We also present some new results on cancellation graphs, which have corresponding implications for neighborhood reconstruction. We are particularly interested in the (yet-unsolved) problem of finding a simple structural characterization of cancellation graphs (equivalently, neighborhood-reconstructible graphs).","type":"string"},"datatype":"string"},"type":"statement","id":"Q528982$62DB7062-A842-400E-ABDE-CB8C60095091","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528982$A16E3536-081F-4D5E-A1B9-ED408946B851","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528982$A5E14F92-3592-4345-9D86-9994A3A9938F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c2243702abc1efa754bcbd2a70f3dd4f5a828a1","datavalue":{"value":"6719978","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528982$BBB3DD02-14F4-404F-B1AB-C8B436CEF467","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"87358badf78ee8b81015673c24e405dcd5968853","datavalue":{"value":"graph products","type":"string"},"datatype":"string"},"type":"statement","id":"Q528982$2C1DC728-5CC0-4674-AAD2-4B391A3B0360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"229adf8371e5ec4b765b87e45634a5fda957368e","datavalue":{"value":"graph reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q528982$F6814413-8C71-4236-88D7-9965EDEA4638","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$B404AA0E-185E-468C-9D0A-04B4C7B6A7E1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"23c18af0ca63ae9d823049ed15f3ccd550ad23bc","datavalue":{"value":{"entity-type":"item","numeric-id":1344609,"id":"Q1344609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$3609C087-4D32-463C-9BDA-797F6E06408C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd6951a45cfdddad3ba3be4ddb12f5c417bdf17f","datavalue":{"value":{"entity-type":"item","numeric-id":3058544,"id":"Q3058544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$37D5A1FD-0425-45D0-847B-16512AA06586","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d543e0e002ccb8d633dfbf8d6e835be577ec4d3a","datavalue":{"value":{"entity-type":"item","numeric-id":3005852,"id":"Q3005852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$D46F5D0B-50D6-45D6-BA32-A75FC2C49193","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe87c952f084b93ea7740099b7636c36558c13bd","datavalue":{"value":{"entity-type":"item","numeric-id":1025517,"id":"Q1025517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$7ED56B67-9330-40A3-A937-DF1CC9DD07CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4dd43fe26f47c6b6ff3655bda44e02c47662ee42","datavalue":{"value":{"entity-type":"item","numeric-id":1943393,"id":"Q1943393"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$B860FD89-DD2C-44F1-B5EB-7840C39A27DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b20274ac1a71b95e67eab06460cb9b542564b3be","datavalue":{"value":{"entity-type":"item","numeric-id":3090474,"id":"Q3090474"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$21764A31-F3E5-4898-8575-80964FD1BAA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de7f8e44eaac7f5c9f9a141578b38f04e8773054","datavalue":{"value":{"entity-type":"item","numeric-id":1367047,"id":"Q1367047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$95CCD23A-4EE1-40BC-9D8F-3499BF818688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7e631c62aa5cbbce88c3fe7a12dc803f1cb78bb6","datavalue":{"value":{"entity-type":"item","numeric-id":5500493,"id":"Q5500493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$8DCE6248-35B7-43B6-AC81-B238239B814C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c0aa581f1dfafe6b6132e86e1f518d648497852","datavalue":{"value":{"entity-type":"item","numeric-id":2547900,"id":"Q2547900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528982$E20BC576-3934-4AD3-9ACD-CF7E6CAB9BE3","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"e88bd1838aa85163cf48d5dd29dee9cdf9ace4b5","datavalue":{"value":"bafkreieta4xxt2yth277gtde3zndyoyblvy7agztzidhoxp5ssnzbjjz6e","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528982$7F19CFE7-ACF0-4CED-985E-4CB697650457","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a61628628f0998238f6ceaaf02fd6e0684cbca9","datavalue":{"value":{"entity-type":"item","numeric-id":2214326,"id":"Q2214326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dd965aa44096df1f294e488ed7092e409341008","datavalue":{"value":{"amount":"+0.8377320766448975","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528982$AE4DDF96-11DC-49C7-ABBF-C41AC121B9C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c447bbe0eab8d1e79b97b4328d48c69718a6000","datavalue":{"value":{"entity-type":"item","numeric-id":1025517,"id":"Q1025517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6147d33d6f1f83c0a67a4b996629559c2229416","datavalue":{"value":{"amount":"+0.8349851369857788","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528982$78DDF01B-EF6B-4240-93CB-1D888A235819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5af564738500c4b316beb6fac1c863ca35585e26","datavalue":{"value":{"entity-type":"item","numeric-id":3527535,"id":"Q3527535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fa10cbb800dbe22e6e6f6659ea87043ba59ddc97","datavalue":{"value":{"amount":"+0.8020226359367371","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528982$6F52F1A9-CD11-493F-940C-274105D03ADC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd5deac7a322a39d13ec51909e7f6d7e5f735e7d","datavalue":{"value":{"entity-type":"item","numeric-id":3813841,"id":"Q3813841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa0c1555d17b1596f4f165bc9a5a38c4b8da5b32","datavalue":{"value":{"amount":"+0.7992168068885803","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528982$309B255E-B8C8-4773-B111-D9E8A60D0F54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c94a689ab119ad46abf31ca287235c4d92562c8","datavalue":{"value":{"entity-type":"item","numeric-id":973141,"id":"Q973141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e2c4e9b4d373c04dc025d01b73cafbecfb46f9b","datavalue":{"value":{"amount":"+0.7920331954956055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528982$4C41198F-6BC9-4545-95AC-0B9A347804B6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Neighborhood reconstruction and cancellation of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Neighborhood_reconstruction_and_cancellation_of_graphs"}}}}}