{"entities":{"Q540027":{"pageid":541794,"ns":120,"title":"Item:Q540027","lastrevid":62604903,"modified":"2026-04-11T07:13:23Z","type":"item","id":"Q540027","labels":{"en":{"language":"en","value":"The complexity of obtaining a distance-balanced graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5902979"}},"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":"Q540027$5A32A566-1A6F-408C-91E3-2501F39A1C86","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"440061048355ac55bbfa6436e29ae8f8f2fbd0e7","datavalue":{"value":{"text":"The complexity of obtaining a distance-balanced graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540027$4A3CCC9D-977D-4E41-A038-91618F13584D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"39dfc04d8771284b45bf07c2561b7e045af2d626","datavalue":{"value":"1218.05043","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540027$391E9F0A-41B7-42C8-BD7B-43C986EFF316","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b3bfcf8a87928cedc4cb6acccce2badfe60d93b9","datavalue":{"value":{"entity-type":"item","numeric-id":262252,"id":"Q262252"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540027$A598E20D-E207-48B7-B44B-A658CE27AD4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aa5f051342a5440c3074d00f5544914fbf1c0847","datavalue":{"value":{"entity-type":"item","numeric-id":540026,"id":"Q540026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540027$791FFDC2-6DA7-4558-BFA0-64684709BEA0","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":"Q540027$C8384575-0631-427E-8396-21518E2D41BB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca412915d48bc02df19cbc26b81271d64e23ee32","datavalue":{"value":{"time":"+2011-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q540027$93F23931-3FEF-447D-BB69-8AC21EF405AD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7f778818ef89f7c09826251b9986da75107ae1e2","datavalue":{"value":"https://eudml.org/doc/230327","type":"string"},"datatype":"url"},"type":"statement","id":"Q540027$38E7AE0E-C302-45FE-BC76-5A269A4950DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"cd1c78618d53b1a6a5c596d4b8b5c72877bc8a2d","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p49.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q540027$21D7A9F6-5332-4DA0-9246-8F6FA94076E7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e26c0202623a208d1bc6baa81f05be7d3e55f24f","datavalue":{"value":"Summary: An unweighted, connected graph is distance-balanced (also called self-median) if there exists a number \\(d\\) such that, for any vertex \\(v\\), the sum of the distances from \\(v\\) to all other vertices is \\(d\\). An unweighted connected graph is strongly distance-balanced (also called distance-degree regular) if there exist numbers \\(d_1, d_2, d_3, \\cdots \\) such that, for any vertex \\(v\\), there are precisely \\(d_k\\) vertices at distance \\(k\\) from \\(v\\).   We consider the following optimization problem: given a graph, add the minimum possible number of edges to obtain a (strongly) distance-balanced graph. We show that the problem is NP-hard for graphs of diameter three, thus answering the question posed by \\textit{J. Jerebic, S. Klav\u017ear} and \\textit{D. F. Rall} [``Distance-balanced graphs,'' Ann. Comb. 12, No.\\,1, 71--79 (2008; Zbl 1154.05026)]. In contrast, we show that the problem can be solved in polynomial time for graphs of diameter 2.","type":"string"},"datatype":"string"},"type":"statement","id":"Q540027$5A686C2C-FE13-4309-B00A-2847841EF10C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540027$81BF2815-3BEE-495B-86E8-2F25772B804B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540027$32EBF722-2550-4909-B85E-42514FE49C31","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ed3b47e8b79f9712e6cbe4f18e3241b561c8c92d","datavalue":{"value":"5902979","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540027$E92D0CC2-5362-4DCD-8E03-88CFEC1F48E0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d9bef146c6618f51a9cde7c9c24a179ed6807d41","datavalue":{"value":"distance balanced graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q540027$971A89A9-8FA5-47ED-A14D-BB745F1502E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fbd71df9a32a173b87b80fd1e3c9a754e667787e","datavalue":{"value":"self median graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q540027$2DFAEF63-889B-4CA9-BC49-A5B6C728A04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9df217b1fcc74de5dbf28297563ba87ada335cb5","datavalue":{"value":"sum of distances","type":"string"},"datatype":"string"},"type":"statement","id":"Q540027$9AD2765F-0E37-4270-BA1C-A5AF1D546081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"453ae3c68a475fc649edb944b85581e778dc64da","datavalue":{"value":"distance degree regular","type":"string"},"datatype":"string"},"type":"statement","id":"Q540027$A9468BD0-4E63-44AF-A808-918999B659B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ad4d10806e4bdb98da58431aa37e48e58bb6ab18","datavalue":{"value":"optimization problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q540027$20BC8EA9-BBDA-448A-8604-810F92CE49AA","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":"Q540027$3CD5AF5B-AA39-436F-A0D6-B9297CFC817B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ddb79b1d8796dc86b25aa1c2c2a96cf93b75a349","datavalue":{"value":"bafkreiccbbe2vqgs64kzux7dg3csijydo32k7nhreotqnyq6eq3vm3odxi","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540027$7F48250D-2411-45EF-B6F5-D82FB19F4E2E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1bb55a8ce1d6ae75c0d183626b9dba934aefec3","datavalue":{"value":{"entity-type":"item","numeric-id":2674566,"id":"Q2674566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"986dae0e19b86185061b129173929a9d4750d9be","datavalue":{"value":{"amount":"+0.9338411","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":"Q540027$4A9AAD12-11CD-4EE1-B36A-5AFC33FC6B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e27df2f89ed068dc4c4a244ab07e5eb60657f7b","datavalue":{"value":{"entity-type":"item","numeric-id":966128,"id":"Q966128"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22336eb90a5c8ffc3fff40b4018f6e72c54f6cce","datavalue":{"value":{"amount":"+0.9335921","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":"Q540027$6366425E-9C5D-4491-BD1B-2B2201D40A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb82771f8ae375421077ed2a5c06b7eb47e76a14","datavalue":{"value":{"entity-type":"item","numeric-id":5402913,"id":"Q5402913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e00cd6524fa67452a8a1bb82f447735602bc6023","datavalue":{"value":{"amount":"+0.91850114","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":"Q540027$62239C1F-C309-4869-B04F-17067BB44761","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f44bc291d55608ef80103f043f35bee6eece9fe6","datavalue":{"value":{"entity-type":"item","numeric-id":1752599,"id":"Q1752599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"858f87a1853551e29e44221bbaf2d24ce405dafd","datavalue":{"value":{"amount":"+0.91602933","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":"Q540027$55C56C71-4BF8-4AFC-A627-FBCBEDF6A700","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"720848d339a2e8f7ea4fee6d0ab5771c057461e3","datavalue":{"value":{"entity-type":"item","numeric-id":4921405,"id":"Q4921405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0921b6a657d8453e5f4e8df55db4a9561739ae0c","datavalue":{"value":{"amount":"+0.9105915","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":"Q540027$E659D4C0-3FD5-44B3-8A7F-EC9198575C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df1bbdabdab38050123b91e6d4b0616e397301f5","datavalue":{"value":{"entity-type":"item","numeric-id":938213,"id":"Q938213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5315d8a475246c39f1065feb635fe1bdd22076b2","datavalue":{"value":{"amount":"+0.907079","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":"Q540027$5616A594-2A51-4B4C-B3DA-856BECC22DE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08269cf71a00835a8eccb256152f0b532112854a","datavalue":{"value":{"entity-type":"item","numeric-id":4605795,"id":"Q4605795"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7815719b3e219d8912f7cef8cb407e96efb5d5eb","datavalue":{"value":{"amount":"+0.9025823","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":"Q540027$F07123ED-0786-41EC-AF41-8172A845A829","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70ed220c5f950615e61fa330ceef38189b647eb9","datavalue":{"value":{"entity-type":"item","numeric-id":5134457,"id":"Q5134457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"335e71a0503b1b3f136b9348c585d08095ad9ab1","datavalue":{"value":{"amount":"+0.9024214","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":"Q540027$D873969C-8B94-4489-B634-4827B8C1E4C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a6246954bfdb219ea64f1b06652e3c0403c70bc","datavalue":{"value":{"entity-type":"item","numeric-id":4993964,"id":"Q4993964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43bd6e395ef04ca91bdc300550da5c3a281d359a","datavalue":{"value":{"amount":"+0.9013054","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":"Q540027$A33D6EC4-2CFF-418E-AC2B-EB00DB2452BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1a65be0396ceafec692ff61443ada4b840c84556","datavalue":{"value":{"entity-type":"item","numeric-id":1758170,"id":"Q1758170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcebe185b4150ba14e96b6c7c8c8a6caca1d55dd","datavalue":{"value":{"amount":"+0.90088856","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":"Q540027$89F0E634-57BA-4988-96FC-1CFEDC027F9E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The complexity of obtaining a distance-balanced graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_complexity_of_obtaining_a_distance-balanced_graph"}}}}}