{"entities":{"Q1127872":{"pageid":1138621,"ns":120,"title":"Item:Q1127872","lastrevid":66191052,"modified":"2026-04-12T08:09:54Z","type":"item","id":"Q1127872","labels":{"en":{"language":"en","value":"Maximal and minimal vertex-critical graphs of diameter two"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1186388"}},"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":"Q1127872$17616625-0D64-4529-B54C-6FB7F1B78AB6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"97cd7d9fa8f80c123b888d901f315cfbf8d9c937","datavalue":{"value":{"text":"Maximal and minimal vertex-critical graphs of diameter two","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1127872$9F9B8EBE-ED1F-433F-A072-8E5EDD56B6D6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eb60aac02b95a19a02b61dac64f30d69dc15c19e","datavalue":{"value":"0904.05054","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1127872$9FFD17E5-C51F-4C64-ADDA-42696D6E2531","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"34f22a6729f35fdca6b93da9cf3e98fe7a07cdad","datavalue":{"value":{"entity-type":"item","numeric-id":189756,"id":"Q189756"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$7A8E584A-D177-4E93-8762-8A79ECF93788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$2F96AABA-FA26-4461-9F20-FB3FEEDAAF98","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$DE7E1354-5EF1-4835-9631-E75F8D07B2F2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a0d45ee9df76ca8b87880e2aeb203d027e791992","datavalue":{"value":{"time":"+1998-09-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1127872$0DE69A14-617F-4B05-8F25-CC38AC03EB9A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6566f75792af56f670f431786393c7778fbf168","datavalue":{"value":"https://semanticscholar.org/paper/3ea163c299198a1823acf781324e4008b99ee204","type":"string"},"datatype":"url"},"type":"statement","id":"Q1127872$C95D0B4E-D22F-4A25-A41E-7C95D743F7EE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cc12ebc49b37b75c25382640c40c28af05413463","datavalue":{"value":"A graph is vertex-critical if deleting any vertex increases its diameter. We construct, for each \\(\\nu\\geq 5\\) except \\(\\nu= 6\\), a vertex-critical graph of diameter two on \\(\\nu\\) vertices with at least \\(\\frac 12\\nu^2- \\sqrt{2}\\nu^{\\frac 32}+ c_1\\nu\\) edges, where \\(c_1\\) is some constant. We show that such a graph contains at most \\(\\frac 12\\nu^2- \\frac{\\sqrt{2}}{2} \\nu^{\\frac 32}+ c_2\\nu\\) edges, where \\(c_2\\) is some constant. We also construct, for each \\(\\nu\\geq 5\\) except \\(\\nu=6\\), a vertex-critical graph of diameter two on \\(\\nu\\) vertices with at most \\(\\frac 12 (5\\nu-12)\\) edges. We show such a graph must contain at least \\(\\frac 12 (5\\nu-29)\\) edges.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1127872$ACFF2EE0-9516-4C66-9805-C7D639576B6F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1127872$44B291A3-7FAA-4E1C-A169-6A1B00C9CBBB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"83185e8975e9d6585f438b0649e3a871f3aed484","datavalue":{"value":"1186388","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1127872$C34188AD-ECBB-42CB-8694-A9571E633C11","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cd227adb1378edbe90691dff18511cebed6b0036","datavalue":{"value":"diameter","type":"string"},"datatype":"string"},"type":"statement","id":"Q1127872$C686F00F-A38E-41EF-9FBB-AD4F4E9ED6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"54145a1c4a82b2f7b1704c92ef20f7093307c734","datavalue":{"value":"critical graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1127872$3422DD1D-16E5-41FD-9935-607D423AD541","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b021e17aa5d68733d2f8043d2f5b350f63304dc","datavalue":{"value":"number of edges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1127872$F52F6D1C-A45B-4E64-98C0-9B07AB6B40ED","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":"Q1127872$3F231863-C98D-4C9C-9022-A633D03D765E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"90c01d3b5b981d82880d0bc49ae33724bd03f48c","datavalue":{"value":"W2144012227","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1127872$64430227-3829-44D1-92C9-6775DA660D29","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddc79b5a848c028c0929256625b5d80270f00d13","datavalue":{"value":{"entity-type":"item","numeric-id":1356444,"id":"Q1356444"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$253991BC-1BB2-4884-903F-9C59CA9C604C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe662fba77a2a64c285b45427bf1c4b90c1449d6","datavalue":{"value":{"entity-type":"item","numeric-id":3469118,"id":"Q3469118"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$4BB14B35-52F8-4A7B-8127-545F2E53D826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$840A2A1D-AC77-42BD-8A9B-6FF8F31CE2C9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42952209e319512f666496c2f8fe07f18d3940c5","datavalue":{"value":{"entity-type":"item","numeric-id":4406067,"id":"Q4406067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$EDD88E4F-14CC-4B7F-B449-736FE789DB83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6685823d9240be834878fd92cf41da3dc7f30da2","datavalue":{"value":{"entity-type":"item","numeric-id":4359591,"id":"Q4359591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$9D236668-C1EB-444D-B43C-E5850759B724","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39474eb107c730b313b9bda8f9c5f3e05d5cbf1a","datavalue":{"value":{"entity-type":"item","numeric-id":3966172,"id":"Q3966172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$30A0FA75-EC7C-453D-9414-959873560A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa2ca5d2235c1a860c322b82811fe6515e32a16e","datavalue":{"value":{"entity-type":"item","numeric-id":4115166,"id":"Q4115166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$1E501A9B-D3D5-4BE3-8B88-37D310772687","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40d87b37181da92e149d22201b4ce14b1954cf2a","datavalue":{"value":{"entity-type":"item","numeric-id":4079637,"id":"Q4079637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$96728C1A-0AD9-4400-9E6E-2AE426B9ADFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5dd8bcefbd1f77068a352a624f78128482912485","datavalue":{"value":{"entity-type":"item","numeric-id":3910007,"id":"Q3910007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1127872$A72B46D2-6D50-4A0C-BECB-BBCB70937DE6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d206247798c7b64522e1fdcc0c1b7fd7c034e2f5","datavalue":{"value":"10.1006/JCTB.1998.1852","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1127872$BABA02EF-1CE4-48BF-8E5C-47920F2F458C","rank":"normal"}],"P1643":[{"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":"f7852813dda4bff1384a60c6c021b0162b52cace","datavalue":{"value":{"amount":"+0.8866229057312012","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":"Q1127872$C5405D7F-E464-4698-AC18-C44F2CBCCD68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1140977fa0c557ffe66c4f159af9d37a861ce2ca","datavalue":{"value":{"entity-type":"item","numeric-id":4406067,"id":"Q4406067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a35b8d528fe479769990d0143a0e669b4d2804a","datavalue":{"value":{"amount":"+0.874372661113739","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":"Q1127872$A0A94270-5B68-4889-B746-F5603528F72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44538a6552364ef48b108ed75afdd71ee7cd04a4","datavalue":{"value":{"entity-type":"item","numeric-id":5711697,"id":"Q5711697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f211755159fed91443146a78684e83818d2ec41","datavalue":{"value":{"amount":"+0.8731815814971924","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":"Q1127872$EE8208F6-A1BD-4045-89DD-71A5666F51D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4f9be34d05c9f4a5cbb8fc33bc5207f2e7a9e8d8","datavalue":{"value":{"entity-type":"item","numeric-id":4780517,"id":"Q4780517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78d021e68316c8dc133b2aa06cb42aa4cbfafc93","datavalue":{"value":{"amount":"+0.8631879091262817","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":"Q1127872$C4B14EB1-E5F0-410C-8CF3-02897703EAB8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximal and minimal vertex-critical graphs of diameter two","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximal_and_minimal_vertex-critical_graphs_of_diameter_two"}}}}}