{"entities":{"Q1892828":{"pageid":1903570,"ns":120,"title":"Item:Q1892828","lastrevid":69207774,"modified":"2026-04-13T05:28:38Z","type":"item","id":"Q1892828","labels":{"en":{"language":"en","value":"On the optimal vertex-connectivity augmentation"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 767677"}},"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":"Q1892828$5927B531-BBF7-4A5F-A531-22299ADE1731","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cf02feb010c0d43de2fbbbca9527e60352cde8bd","datavalue":{"value":{"text":"On the optimal vertex-connectivity augmentation","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1892828$F7C7CD09-D815-4264-BA28-55A942584620","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"67441dc0beff032a9698e11066fa10be14e264b1","datavalue":{"value":"0824.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$EDF9F88B-7AB3-4E70-BA85-5BDF0B4D036F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"720a2470955600a0e199ea4312c70a5e6b991176","datavalue":{"value":{"entity-type":"item","numeric-id":226798,"id":"Q226798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892828$A5DB6459-88E9-4D33-991A-30E350BB49BA","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":"Q1892828$2B28C6C1-C7A6-4511-A405-177E81A9F138","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"89939404571a8a457f4efe42bf31156c65cd7105","datavalue":{"value":{"time":"+1995-07-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1892828$4B07EDE1-A909-40DE-925F-1AE8B87E6986","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2621684cefab998b3ded37c44a7544859caf5596","datavalue":{"value":"The optimal vertex-connectivity augmentation problem denotes the task of finding the minimum set of edges that should be added to a graph to increase its vertex-connectivity. The cardinality of such a minimal set for a graph \\(G\\) is denoted \\(m(G)\\). The author considers simple graphs and proves that for any \\(k\\)-connected graph \\(G\\) \\((k\\geq 2)\\),  \\[ \\max\\{b(G)- 1, \\lceil t(G)/2\\rceil\\}\\leq m(G)\\leq \\max\\{b(G)- 1, \\lceil t(G)/2\\rceil\\} k- 2, \\]  where \\(b(G)\\) denotes the maximum number of components that can be achieved by removing \\(k\\) vertices from the graph \\(G\\), and \\(t(G)\\) equals the maximum number of pairwise disjoint minimal tight sets.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892828$B4230C2D-8A42-4567-B845-9D6936D9492C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$5551CF43-912E-4EA2-9B0F-AC9564CA8968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$64261373-2F7E-4085-98B0-A36DCE44FF7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$63189E58-5C92-4153-953B-A5E280205F15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$4856ACFF-7227-4A3C-B6FB-85911FF13F12","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1fd3600f1e1f9c8038598db6447b91756c4c5336","datavalue":{"value":"767677","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$0E6852B7-9880-41FD-8FCD-DA96D204930B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eab55915f41e395e418b6e172f08893469ea82cf","datavalue":{"value":"vertex-connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892828$E64DB912-AE62-444E-9079-6D29E771B90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2363d166b5b9fc791a0d6228cc5a474e45585fdd","datavalue":{"value":"polynomial-time algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892828$0388864A-71FC-4344-BD47-AB6D9B4CFD05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bf7b61429052d7006ca7cf139ef9d49af4b129e2","datavalue":{"value":"optimal vertex- connectivity augmentation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892828$9887E086-E69C-4750-A510-BD3E9C4CCEEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"61f00c95720f5313d1677b58b42c24752ec77eb1","datavalue":{"value":"\\(k\\)-connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892828$5886A07F-0FE7-4142-9FEA-FBF9F64986EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"efeb38a6eefe32b3c68748284ab888c58a8ef68f","datavalue":{"value":"tight sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q1892828$54ECBE63-017E-44EA-A1BA-73971DCFB460","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"56a1ca2701a8ace98397887a83075850e16781d0","datavalue":{"value":{"entity-type":"item","numeric-id":274436,"id":"Q274436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1892828$E81D09E6-0A11-45FC-A87B-B07A005D14B6","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":"Q1892828$2FE59CE8-C34A-4E7A-9B56-24B96171D619","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bc00516f431ca9c1713b879fd530f9d2be992622","datavalue":{"value":"https://doi.org/10.1006/jctb.1995.1002","type":"string"},"datatype":"url"},"type":"statement","id":"Q1892828$AB0C3BF0-2842-47D8-A5C6-03252C0EB32C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c70640ee975abed56ca249a45e5079f5c3208724","datavalue":{"value":"W2048815229","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$5F62FFC8-950E-4917-A4F9-155857CA6303","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93956e6eb6375a41d40a5ab0bd070e5a97a81c29","datavalue":{"value":"10.1006/JCTB.1995.1002","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1892828$213CA19E-B048-437C-A383-2B0CC1FE21B6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d5306a1bb01fe9281223c994627be261070afb4","datavalue":{"value":{"entity-type":"item","numeric-id":2721988,"id":"Q2721988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ab361861c184a500b2c018fa0c9b5d911a3379f","datavalue":{"value":{"amount":"+0.8365989327430725","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":"Q1892828$D0BF8C73-1B79-4586-BA91-3F9D64822718","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d68703cd044bbd46713c2b7d2191c219a5161859","datavalue":{"value":{"entity-type":"item","numeric-id":1407835,"id":"Q1407835"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4b318505307acac064e30fa4739bceaa45a6636","datavalue":{"value":{"amount":"+0.8344217538833618","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":"Q1892828$86A9C2C4-E90F-4C90-A751-38DEAD7C9230","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f833e9b80612e575da742c59d710519de90f8112","datavalue":{"value":{"entity-type":"item","numeric-id":4256090,"id":"Q4256090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2973a2f3957462e6848266e7a0226faca51c7f4","datavalue":{"value":{"amount":"+0.8299883604049683","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":"Q1892828$690E3D31-14F2-40FF-A3C1-B269F9AAC947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"227e54671b4cf7c3ef74156e7660ad3e46e44a24","datavalue":{"value":{"entity-type":"item","numeric-id":2816106,"id":"Q2816106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3001dae0d08e99c2ed7b8bdc8591c106ea846cce","datavalue":{"value":{"amount":"+0.8289705514907837","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":"Q1892828$D86884C7-8206-4FD3-A479-558E051F18A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the optimal vertex-connectivity augmentation","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_optimal_vertex-connectivity_augmentation"}}}}}