{"entities":{"Q2721331":{"pageid":2732070,"ns":120,"title":"Item:Q2721331","lastrevid":82960313,"modified":"2026-05-06T22:33:00Z","type":"item","id":"Q2721331","labels":{"en":{"language":"en","value":"Concerning the number of edges in a graph with diameter constraints"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1612953"}},"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":"Q2721331$27FB81B5-64E1-4EEB-8E5B-14D6BA499952","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ef149edb65ef5ca9fc4b548ff805e9cc344fb896","datavalue":{"value":"0982.05045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2721331$160F2BDE-2C72-48EE-AE8C-66A2B66CE852","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e620da4866036e8f0d7f7254068b12c32cb4afa0","datavalue":{"value":{"entity-type":"item","numeric-id":328466,"id":"Q328466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2721331$918DF93E-695F-49FD-99E5-8BDFEB4B2220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b4c6681c3147b5ea175e9bd53e2b91cf1b565a99","datavalue":{"value":{"entity-type":"item","numeric-id":1055429,"id":"Q1055429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2721331$34DE5F7D-9DFA-48AB-8976-CF8F22EC5814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8a49b75d1c698d7bc3c2794e96355a37b37c443f","datavalue":{"value":{"entity-type":"item","numeric-id":6055411,"id":"Q6055411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2721331$FA3DC5DF-BFF5-46F5-BF41-64B530E3A004","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d18439a648c68971434e67c4d3438eb872bd034f","datavalue":{"value":{"time":"+2002-04-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2721331$1921CB21-88B0-43F2-86DB-D3C89773C478","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2721331$38BDB82C-C081-4A97-B16F-C19DBF7B1833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2721331$547102F3-D582-4BAB-BFD9-16D846E5D29C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9e8b456191081cdc6633e53994d91b3b097f3c73","datavalue":{"value":"1612953","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2721331$117F2372-8DD1-459B-A5F3-A5878923130D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54145a1c4a82b2f7b1704c92ef20f7093307c734","datavalue":{"value":"critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2721331$445CD78A-9FD3-4446-B396-632B55EBECDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q2721331$C5D96F7A-DCF6-4FAE-98D8-62558C6E526B","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":"Q2721331$8798D3B3-C8DC-4CFE-8B51-7CB41B1DEACE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ef43a0ee4387f4a18e82e7370291f7c88b877a68","datavalue":{"value":{"text":"Concerning the number of edges in a graph with diameter constraints","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2721331$90D73F0F-A375-4681-B1E2-B0EB2486D565","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0b959db617f3356e1c1271425a63cf65fe67e897","datavalue":{"value":{"entity-type":"item","numeric-id":6558930,"id":"Q6558930"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2721331$E88BBEF6-F7AA-463F-8007-FB78332206B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"95d3335bac12a2f4942c8cb41998b5de4afc9a90","datavalue":{"value":"The authors study several problems related to the number of edges of a graph with diameter constraints, e.g. the following problem: Let \\(k\\geq 2\\) be an integer. Given a graph \\(G\\) of diameter \\(k\\) find a spanning graph \\(H\\) of \\(G\\) of diameter \\(k\\) of minimum size. The authors show that this problem is NP-hard. Moreover, they give four efficient heuristics for this problem for \\(k=2\\). They also conjecture that the number of edges in a critical graph of diameter \\(2\\) with \\(n\\) vertices is at most \\(\\Delta(n-\\Delta)\\), where \\(\\Delta\\) is the maximum degree.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2721331$8F040953-DEE8-4FDF-95E8-1A47DA419E5C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"537fadaa81863f07c95f9ce70feadc229f68c3c5","datavalue":{"value":{"entity-type":"item","numeric-id":860608,"id":"Q860608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2721331$060BBC79-5819-4E6A-BBE3-E2516841EA46","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3acd871ff7d13f53c729247dfebff1bef4834296","datavalue":{"value":{"entity-type":"item","numeric-id":3470486,"id":"Q3470486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cf34f4762861e4ee8bb3801e21b735677dd51062","datavalue":{"value":{"amount":"+0.8122527003288269","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":"Q2721331$C7508624-84F8-41B0-8A34-4F2A65A07658","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11e824e3c383b5151a1831878c45909719d7da0e","datavalue":{"value":{"entity-type":"item","numeric-id":905895,"id":"Q905895"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff796645ef3597d840aacd57509f0b4e86128f08","datavalue":{"value":{"amount":"+0.806873619556427","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":"Q2721331$3906C0AE-0DAD-46D2-9EB8-41D49B4FDDBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4bd585f6b948c928927fac9e406a7c2f81c1dcc9","datavalue":{"value":{"entity-type":"item","numeric-id":1096642,"id":"Q1096642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490e360236a4f14f56bdf7da103945dbb6d22f81","datavalue":{"value":{"amount":"+0.8064746260643005","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":"Q2721331$0E6BFB3E-4E99-4ED8-9FBD-FD6D56933DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"351fb4e3f1004c488e89a0a16f965c0f2a9cdb76","datavalue":{"value":{"entity-type":"item","numeric-id":1356444,"id":"Q1356444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0218387bda9c13968cfa220720db4c3c43648e01","datavalue":{"value":{"amount":"+0.7859998345375061","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":"Q2721331$3B1A942F-4A15-4BCC-89B3-628C344B8ACE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47cfeb11e6841abfcc803c12cff64cbe17794e9b","datavalue":{"value":{"entity-type":"item","numeric-id":4359591,"id":"Q4359591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a3fbf2c8be442c07f367bb4b1b4488bf6521cde","datavalue":{"value":{"amount":"+0.7846646904945374","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":"Q2721331$D880D0B6-2CE9-4754-9AC3-793B23893B4A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Concerning the number of edges in a graph with diameter constraints","badges":[]}}}}}