{"entities":{"Q2470472":{"pageid":2481215,"ns":120,"title":"Item:Q2470472","lastrevid":78716396,"modified":"2026-05-06T12:16:10Z","type":"item","id":"Q2470472","labels":{"en":{"language":"en","value":"A conjecture on the reconstruction of graphs from metric balls of their vertices"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5235189"}},"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":"Q2470472$E636DF8E-5067-40DC-9E0B-E1B4B5377C4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"167aba64d68109d06755f4e0760f089b0527d84e","datavalue":{"value":{"text":"A conjecture on the reconstruction of graphs from metric balls of their vertices","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2470472$A454B136-AECD-4E3A-81C3-475294903526","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0c5b950d1051f8e16189bc5ea94b8e25f924a488","datavalue":{"value":"1142.05056","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$F2858AEE-A1A5-4CC5-BBC5-86817AB3472D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2470472$567E27A6-112A-43A4-B704-0B363745DD4A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3af390bcdc6b2953e54159e2d83c5dea647d27b4","datavalue":{"value":{"time":"+2008-02-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2470472$2490EA26-6C90-4CFF-9C2D-9FEB464A8DF1","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e572cefbd14de78032af5240fd3c65319bfac4fd","datavalue":{"value":"This very nice paper investigates an interesting variant of the graph reconstruction theme. Let \\(G\\) be a labelled graph. For any vertex \\(v\\) in \\(G\\), the ball \\(B_r(v)\\) for \\(r\\geq 2\\) is the set of vertices at distance at most \\(r\\) from \\(v\\) with \\(v\\) itself indicated as the centre of the ball. The question is to reconstruct \\(G\\) identically from the balls \\(B_r(V)\\) for all \\(v\\) in \\(G\\). The author considers the number \\(t(r)\\) which is equal to the minimum number \\(t\\) such that a simple connected graph without terminal vertices and with girth at least \\(t\\) is reconstructible from the balls \\(B_r(v)\\). Consideration of the cycle with \\(2r+2\\) vertices shows that \\(t(r)\\geq 2r+3\\). The author conjectures that, in fact, \\(t(r)=2r+3\\). The main result of the paper is the upper bound \\(t(r)\\leq 2r+2\\lceil (r-1)/4 \\rceil +1\\) which, in particular, implies the conjecture for \\(r=2,3,4,5\\). It is also proved that \\(t(r)=2r+3\\) if \\(G\\) has no terminal vertices and apart from the balls \\(B_r(v)\\) one knows at least one edge of \\(G\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2470472$573C2888-FC4D-4488-803B-1AB761286F6F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3b6fe1f213720dd616a466b95779de3e7abac963","datavalue":{"value":{"entity-type":"item","numeric-id":394315,"id":"Q394315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2470472$86BAE911-1103-4149-8D77-66406DE106ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$03C90206-8B51-417C-9299-788E9BAC58F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5333d0205ccf54f8482367bfadbaa8f4afc5f8fb","datavalue":{"value":"05C78","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$24EE0634-9B6C-4E3D-A7F1-1F8B139AC1B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ec7b1388aecb3e008934231390904c32973e4335","datavalue":{"value":"5235189","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$D02F5E8C-517C-4DAC-BACD-37B0CEA0D2E6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"229adf8371e5ec4b765b87e45634a5fda957368e","datavalue":{"value":"graph reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2470472$57CDE66C-149F-46FF-80CB-5EC3A4EFE831","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"db7b7a1da31b99e4cb7d61a10501ba8b494f2baa","datavalue":{"value":"neighbourhoods of vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q2470472$0353C602-2278-4362-8E64-CE08637E4DD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"04efd67b0a8c0b41a9b59d1875c6f7e1514a0278","datavalue":{"value":"labelled graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2470472$B8767077-8415-43CD-81AB-090927D34D9F","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"baea47a4406f6cbf352ad65f2c58f5f457d1c23b","datavalue":{"value":"Q123149540","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$C4AB3E75-053A-4A36-9A80-0589DE1221CF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"133644fff9799313a99458fa03ab15485c084207","datavalue":{"value":{"entity-type":"item","numeric-id":172216,"id":"Q172216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2470472$4461E4DF-31BD-42FD-8A83-CBD30C4E41DD","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":"Q2470472$DE86A9DC-DD01-4F79-895D-A8D9F2251BF6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"110b7d6f332dfb4876a163eef24e1874242e818a","datavalue":{"value":"https://doi.org/10.1016/j.disc.2007.09.027","type":"string"},"datatype":"url"},"type":"statement","id":"Q2470472$F4C62E30-9D72-456F-9D93-428D3E51F240","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"890791a77073be5a28031c1bce0654a9e84b1d6a","datavalue":{"value":"W1995432558","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$276A4C27-37A5-46A5-ABDA-8D72ECA0B89F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e6b9c5d662c0b40af3c11c216c7c50a0bd9f62f","datavalue":{"value":{"entity-type":"item","numeric-id":4414312,"id":"Q4414312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2470472$085A6200-7086-4534-BF42-13A4D3F18FBC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8262a4b85e608e05dba34cfa9f4cb642e45bf51","datavalue":{"value":{"entity-type":"item","numeric-id":3439285,"id":"Q3439285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2470472$9ECF4104-B589-4C0D-AAE3-9AA727296AC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ad2fe8dd86fee87642683d5794ea0cbe53231bb","datavalue":{"value":{"entity-type":"item","numeric-id":3259049,"id":"Q3259049"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2470472$CDE3B0D8-305F-4C24-B67D-12390E732C24","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4a3654174c0b8a5b5d87928ac043a260e212d552","datavalue":{"value":"10.1016/J.DISC.2007.09.027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2470472$695DFF6A-987F-427E-8B15-3DEE13DF1939","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"692b7cd3d8311be3c31bc746caa4f23a2948f0be","datavalue":{"value":{"entity-type":"item","numeric-id":3469125,"id":"Q3469125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f7d7b988092a6cc44ba2ff7dad631f9a785d2954","datavalue":{"value":{"amount":"+0.8903812","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$B99E0CBB-D139-4642-85C3-F56A85E2FD76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"681b12930becd86ca2f17887d3f0af0c44f69cf1","datavalue":{"value":{"entity-type":"item","numeric-id":3636215,"id":"Q3636215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9482f33c1a1b04c295221ad7afc8098488430d80","datavalue":{"value":{"amount":"+0.88730335","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$D692C9B7-AB51-478D-9AD2-95A19F7B71E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d82055788cb8862532211c629cf4f414dce739c9","datavalue":{"value":{"entity-type":"item","numeric-id":2509541,"id":"Q2509541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deee73dd8299a63145c4d2f4c9f77eb823f63b3c","datavalue":{"value":{"amount":"+0.8868797","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$CABBE17A-25C7-46AC-92FE-A98A3477C790","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b876ce123f2124c98bf884341964be2f385e962","datavalue":{"value":{"entity-type":"item","numeric-id":2138987,"id":"Q2138987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cc09d9fc3639c66ebcab06bd7b8da1a7fb54e8a","datavalue":{"value":{"amount":"+0.8857529","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$F8C874E3-6298-4F56-9CD2-2BF1FDB02746","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c214619ab00458c131405da6fb44c47de3d1c915","datavalue":{"value":{"entity-type":"item","numeric-id":2800593,"id":"Q2800593"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ea5675e02b563fbdf50ed7a07a84ca7b09b0c48","datavalue":{"value":{"amount":"+0.88528883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$18D3CECE-EA3A-4180-879B-C127A4B65EEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b5b03ffb8697d58d351145e7d560ffc5659c2b3","datavalue":{"value":{"entity-type":"item","numeric-id":3504736,"id":"Q3504736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c59242957aee8b66ca458181e23148743ab42eab","datavalue":{"value":{"amount":"+0.88304585","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$362F0AD8-BF0F-49AE-B869-E00A0F3F1B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5bf36c5e5b82fc2c3d77f4d9b2cd7aa58273055c","datavalue":{"value":{"entity-type":"item","numeric-id":4383335,"id":"Q4383335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c59a7666c432a6bb630ec2f3b66ae359b4ce2784","datavalue":{"value":{"amount":"+0.8821894","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$818D6ED8-009F-4EAE-A7B5-1F9722272656","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23d661ffcdef3896c937fad77c005910b7eee29a","datavalue":{"value":{"entity-type":"item","numeric-id":3765814,"id":"Q3765814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8e7a8762e4b61546aa8242178d45e471f530d806","datavalue":{"value":{"amount":"+0.8820574","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$F426FE50-6871-4CD6-A744-E088A05796CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eecfdef8ee2fc8b95ae93beb5078f0ce9611f1bb","datavalue":{"value":{"entity-type":"item","numeric-id":5577688,"id":"Q5577688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1f123986d44471e00d0f3eb55f39416001922b54","datavalue":{"value":{"amount":"+0.8817879","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$DD6143B1-339D-4D88-8515-EE43C4190512","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2dfedc49fc8f3a0768adf4fd5d6d3db8fc15ab4a","datavalue":{"value":{"entity-type":"item","numeric-id":2935256,"id":"Q2935256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bc6cb00d830c145b4adfa726d2407b72c08ee726","datavalue":{"value":{"amount":"+0.87978184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2470472$31033C92-7D4B-41C9-99B3-32FF79FC5203","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A conjecture on the reconstruction of graphs from metric balls of their vertices","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_conjecture_on_the_reconstruction_of_graphs_from_metric_balls_of_their_vertices"}}}}}