{"entities":{"Q1613484":{"pageid":1624224,"ns":120,"title":"Item:Q1613484","lastrevid":72343158,"modified":"2026-04-14T04:15:53Z","type":"item","id":"Q1613484","labels":{"en":{"language":"en","value":"The average connectivity of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792414"}},"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":"Q1613484$D25C7391-F893-4727-A93B-DF6481D1D867","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d1a6db445821a0617d7c7c680c541582a1e3cc81","datavalue":{"value":{"text":"The average connectivity of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613484$2BBBDD31-405C-4EE8-B4D7-1E3A08083093","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ad17f7dbb9b26301ae70e509065f024c57fb4fc","datavalue":{"value":"1002.05040","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613484$2DBE8F05-4D38-4D4E-91D3-A8A3B760096B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3665d430a6fc4534eea12bfe44089b55fb29f3b8","datavalue":{"value":"10.1016/S0012-365X(01)00180-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613484$AD3C45B9-94BF-4B25-A9E0-937FE6674629","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91903505496a19b56b6bf18a545dc8fd83a87717","datavalue":{"value":{"entity-type":"item","numeric-id":1126280,"id":"Q1126280"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613484$6EF6C8FA-CAE6-4DBB-A097-AF5F51DB5338","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f35420b14e006c4a26de46d6172502a88cc18a63","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613484$004E8E17-9F92-4482-8DC1-1424F3AFAB62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7d463e7ee2ac1c592e0cdfb8892462cb19b9c9c","datavalue":{"value":{"entity-type":"item","numeric-id":1379515,"id":"Q1379515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613484$59ECC30B-C786-49C7-B7C0-C2E2103A428B","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":"Q1613484$E9CA3956-685E-4B27-8711-55B6277DB16B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613484$D74A3D68-431D-4588-B7BD-F822D0644C1D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"42b50ea446fcc9a2371770326b1670cda59ac5e3","datavalue":{"value":"For a graph \\(G=(V,E)\\) with \\(u,v\\in V\\), let \\(\\kappa_G(u,v)\\) denote the maximum number of internally disjoint \\(uv\\)-paths in \\(G\\). Thus \\(\\kappa(G):=\\min\\{\\kappa_G(u,v):u,v\\in V\\}\\). Define average connectivity of \\(G\\) to be  \\[ \\overline{\\kappa}(G)=\\sum_{u,v\\in V}\\kappa_G(u,v)\\Biggl/{|V|\\choose 2}; \\]  it is computable in polynomial time. Upper bounds for \\(\\overline{\\kappa}(G)\\) are given in terms of the independence number, the degree sequence, and \\(|V|\\) and \\(|E|\\), respectively, this last bound being sharp. Theorem 3.1: If \\(\\overline{\\kappa}(G)=\\kappa(G)=k\\), then \\(k\\geq 1\\) implies \\(\\kappa(G-e)<k\\) for all \\(e\\in E\\), and \\(k\\geq 2\\) implies \\(\\kappa(G-v)<k\\) for all \\(v\\in V\\). Three methods are given for constructing graphs satisfying the hypothesis of this theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613484$6C5634E5-B527-45B5-A8A7-F2DA1DD11B86","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613484$DB103999-AAAD-4B53-9CFA-DEA9F9F419E0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2855d6a6dcab3c682ff01b92cdb319e34feb18c2","datavalue":{"value":"1792414","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613484$D4617945-68F3-4CAA-B5A8-D4B42AAF2338","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"162ca38bc7bf11915f45f1a2de0d2d72fdfb859c","datavalue":{"value":"average connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613484$33E7E5EE-0BE2-4854-BCEF-A42E70EF67A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a0a1cca67aa9bea46443580d11c460f3f155d0e","datavalue":{"value":"uniformly connected","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613484$FFC2C6E9-E21F-4486-9C09-DE360E68BEC4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2420d8bcf60fc74d0291a3c59f694629f273e260","datavalue":{"value":{"entity-type":"item","numeric-id":426905,"id":"Q426905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613484$ECD227E6-ABD8-44A4-82EE-14B7CE06DE6F","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":"Q1613484$13FB2D6F-E2A6-47FF-8B87-BCBF8C6653DB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f0790be4bc85c3aebb8ea39880dca3add7db33e1","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00180-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1613484$A6F7F64A-4A19-409C-BCE4-B9DF18648EC9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"095ee0c255ff0a3425cc5f879548b3bc2c7b63bf","datavalue":{"value":"W2048460015","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613484$D84BEFB4-7ABC-4D6D-8375-391FC97B75A5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58f2764cd5cb9eb38e3d474959effbc51bc973e1","datavalue":{"value":{"entity-type":"item","numeric-id":390306,"id":"Q390306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"56547d2859621ded52d04f3aac77dbedf102a6ce","datavalue":{"value":{"amount":"+0.9721763","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":"Q1613484$CB5611C0-CAAA-41C8-916A-25E4EEAA12A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8015857c234032b57aff50f426f6de500aea75cc","datavalue":{"value":{"entity-type":"item","numeric-id":2927115,"id":"Q2927115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c68581d10b76a57e2570cf4ee1c0a1dc5f1b39c0","datavalue":{"value":{"amount":"+0.9701139","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":"Q1613484$612EB0A0-697D-4501-B2B6-B2A076D4D818","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90cb6cba0df4738758c70749aab9065891b8b3bf","datavalue":{"value":{"entity-type":"item","numeric-id":1827842,"id":"Q1827842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b936b4faaf17f93f36e62d1163ca4bd9ed3f2bb","datavalue":{"value":{"amount":"+0.96971935","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":"Q1613484$B305E6E4-6A2A-4198-85C9-636E164AFD0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"49ccef8c9679b5129332103dbf424affdf0e1d86","datavalue":{"value":{"entity-type":"item","numeric-id":1406026,"id":"Q1406026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"515bdbae3675579e4c7a67a333a45307dcb8bd6d","datavalue":{"value":{"amount":"+0.957237","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":"Q1613484$0EA6F31D-5DBE-4787-A7EC-3D54A84F8F48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93ead115ed16fd7589686ecab4ecb089c200e33b","datavalue":{"value":{"entity-type":"item","numeric-id":1714768,"id":"Q1714768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"261daab3b1699b136bb6c3ca4dea540635612e64","datavalue":{"value":{"amount":"+0.9498557","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":"Q1613484$2BEE3BC5-2382-48B8-A53A-38F455E4A122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"be73ac5b074c29ff773b48fe6ea5691ab6f76208","datavalue":{"value":{"entity-type":"item","numeric-id":3652548,"id":"Q3652548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"267ecd31987aeb319424bd3b30d8f15d030c21cd","datavalue":{"value":{"amount":"+0.9282246","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":"Q1613484$00A4AEDA-3B22-4478-940A-95F7466F59AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccd6b036024e8182fc17f7499506460884f5db3a","datavalue":{"value":{"entity-type":"item","numeric-id":4645486,"id":"Q4645486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d743d3506d287de34e2a202d7bb6a9073008c0e2","datavalue":{"value":{"amount":"+0.9130722","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":"Q1613484$C9D26DF1-C778-4061-81C7-78CDFE5D3A5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69e12280509f720d6810a55e73849462867b8088","datavalue":{"value":{"entity-type":"item","numeric-id":3567781,"id":"Q3567781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"301891ba434ce451184052ff55bfb49e88af90f7","datavalue":{"value":{"amount":"+0.91247153","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":"Q1613484$53EBD9B4-1589-4345-B3D3-EF27D846CB9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ddc821915e43f0896abfd52bd311fdde3cde5e1","datavalue":{"value":{"entity-type":"item","numeric-id":2043391,"id":"Q2043391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f05f4583b1f27ae9c02cb91d13461ac7a539ac2","datavalue":{"value":{"amount":"+0.9074682","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":"Q1613484$B0DCA550-FBF7-4462-8076-78A09900C165","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dccaaebcff096ed34ad337006252f7817a31853a","datavalue":{"value":{"entity-type":"item","numeric-id":2125229,"id":"Q2125229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f42ed4811a04592838c862c2590fc499cc5cec6f","datavalue":{"value":{"amount":"+0.90740705","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":"Q1613484$E1752AE9-D540-450A-AB78-6CE9778BC2DA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The average connectivity of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_average_connectivity_of_a_graph"}}}}}