{"entities":{"Q6559394":{"pageid":14170549,"ns":120,"title":"Item:Q6559394","lastrevid":55690135,"modified":"2026-02-17T21:05:00Z","type":"item","id":"Q6559394","labels":{"en":{"language":"en","value":"On the minimum size of graphs with given generalized connectivity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7869034"}},"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":"Q6559394$74B8678E-0BD4-41EA-A13E-9A72390F8509","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49d07c5af901a9f1a59ec7226378f46d186f89d7","datavalue":{"value":{"text":"On the minimum size of graphs with given generalized connectivity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6559394$D8E18A8E-6D2E-4B23-918D-3259D9A986EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2650a059d5850a8053913449439a57d33fcd6aae","datavalue":{"value":"1545.05126","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6559394$02166BDE-7C16-4EF5-A6DC-168924697954","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"451c4c03d61d2cd1e2177dd6e22e016578c4e52f","datavalue":{"value":{"entity-type":"item","numeric-id":1627874,"id":"Q1627874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$5530DA7A-04C5-48D5-A531-FA25876AFFCF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca7a3095f2aebf51318bece92ce10f60928cff75","datavalue":{"value":{"entity-type":"item","numeric-id":247915,"id":"Q247915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$5C29621B-1522-437E-99F4-C0C7512F10F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1f6dde031be265f6ad0a54e71ef2fbc43ca12de0","datavalue":{"value":{"entity-type":"item","numeric-id":269717,"id":"Q269717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$B8C65658-01D6-46F4-BE23-507A5A0CFC95","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$EF0C2791-AF5D-4931-903C-FC16807837BE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8f537c6f80ef2272fb77fcdfce306448ca22994d","datavalue":{"value":{"time":"+2024-06-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q6559394$B3946EFB-CC26-440C-AC15-41BEEC54755E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ac9b34a767d4f36ae841f7c13f462a7bcb162fa","datavalue":{"value":"The connectivity \\(\\kappa(G)\\) of a connected graph \\(G\\) is the minimum number of vertices of \\(G\\) whose removal disconnects \\(G\\). By a theorem of \\textit{H. Whitney} [Am. J. Math. 54, 150--168 (1932; Zbl 0003.32804)], \\N\\[\\N\\kappa(G)=\\min_{(u,v)}\\left\\{\\kappa_G(u,v)\\right\\} \\N\\]\\Nwhere the minimum is over the pairs \\((u,v)\\) of vertices of \\(G\\) and \\(\\kappa_G(u,v)\\) denotes the maximum number of paths between \\(u\\) and \\(v\\) in \\(G\\) such that any two of these paths do not share a vertex other than \\(u\\) or \\(v\\).\\N\\N\\textit{M. Hager} [J. Comb. Theory, Ser. B 38, 179--189 (1985; Zbl 0566.05041)] generalized \\(\\kappa(G)\\) as follows: for any set \\(S\\) of vertices of \\(G\\), denote by \\(\\kappa_G(S)\\) the maximum number of trees in \\(G\\) such that any two of these trees do not share an edge and the intersection of their vertex sets is \\(S\\). The generalized \\(k\\)-connectivity \\(\\kappa_k(G)\\) of \\(G\\) is then defined in the spirit of the above equality as \\N\\[\\N\\kappa_k(G)=\\min_S\\left\\{\\kappa_G(S)\\right\\} \\N\\]\\Nwhere the minimum is over the sets \\(S\\) of \\(k\\) vertices of \\(G\\).\\N\\NIn this article, the smallest possible number of edges \\(f(n,k,t)\\) of a connected graph \\(G\\) with \\(n\\) vertices and generalized \\(k\\)-connectivity \\(t\\) is investigated. It is shown that, if \\(k\\) is at least \\(4\\) and \\(t\\) at most \\(n-\\lfloor{k/2}\\rfloor\\), then \\N\\[\\Nf(n,k,t)\\geq\\left\\lceil\\frac{t(t+2)}{2t+2}n\\right\\rceil.\\N\\]\\NIt is also shown that, when \\(k\\) is equal to \\(4\\) and \\(t\\) to \\(2\\), this inequality is sharp. This improves on a bound of \\textit{Y. Sun} et al. [Discuss. Math. Graph Theory 41, No. 2, 409--425 (2021; Zbl 1459.05045)] whereby \\N\\[ \\Nf(n,k,t)\\geq\\left\\lceil\\frac{t(t+1)}{2t+1}n\\right\\rceil \\N\\]\\Nwhen \\(k\\) is at least \\(3\\) and \\(t\\) at most \\(n-\\lfloor{k/2}\\rfloor\\) which, by a result of \\textit{S. Li} et al. [Australas. J. Comb. 51, 209--220 (2011; Zbl 1233.05120)] is sharp when \\(k\\) is equal to \\(3\\), \\(t\\) is equal to \\(2\\), and \\(n\\) is not \\(9\\) or \\(10\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q6559394$2D754AFB-8C91-4EF9-9944-80611D0E139C","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6bf85c4bb2a105038c0abd869ef6c3bee6d7e5b5","datavalue":{"value":{"entity-type":"item","numeric-id":449124,"id":"Q449124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$BF1344B8-AD78-4104-852D-8C36CCCB67E2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6559394$66B4680A-47DC-4A2C-8E80-6FBDCB1376D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7dc0be147dc793dec5b4d43620512b87e8c947ec","datavalue":{"value":"90C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6559394$FA27FBAD-DA47-4771-8F07-D434055DACC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6559394$41F2804C-A015-40CF-967E-719A91915BE4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"549662e40af5535665c778b3748fe24568b80329","datavalue":{"value":"7869034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6559394$1708ECC3-B4B1-4CC6-ACAA-D8490BE91F76","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6559394$EA9CC16D-DBF4-4FF0-8BE8-20130D26C59B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"948f35fe95da9679bf3e8ddc007f448d1eca4334","datavalue":{"value":"generalized connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6559394$7B212354-7100-4A12-BC70-6E389FA41542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5cfc79edf190778c24fdbd9385cfe925d57fbdd6","datavalue":{"value":"reliability","type":"string"},"datatype":"string"},"type":"statement","id":"Q6559394$99F1C611-7B34-4DB3-86B0-944DBCDAEAC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b01b02968c48df9f6d634df64bea355af4ca03","datavalue":{"value":"fault tolerance","type":"string"},"datatype":"string"},"type":"statement","id":"Q6559394$A1FE71D1-69F3-4591-984D-6BC419895D12","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":"Q6559394$83151775-EC76-4350-B7E9-CE0DDD651A2C","rank":"normal"}],"P223":[{"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":"Q6559394$2C0DCAA5-1079-49DD-AEEA-C4542E52DCB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d91ed4a9191e9036fead68516e722460d7a35162","datavalue":{"value":{"entity-type":"item","numeric-id":3057159,"id":"Q3057159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$12BBB4FE-80FA-4FE5-ABC6-9698BEBD7701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43ee458fc56e9f9892b3b11842f7d514f794936e","datavalue":{"value":{"entity-type":"item","numeric-id":512887,"id":"Q512887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$FEF0E3B3-0FC1-4F97-A701-67AC7BF22D62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"788bdd2424aa8d9082631b8f40019d652bafe2a1","datavalue":{"value":{"entity-type":"item","numeric-id":6046875,"id":"Q6046875"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$7D880094-DE8C-4782-80E7-EA0109535788","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b37c29fe3b50eb2874175173ed12658ab44ffae","datavalue":{"value":{"entity-type":"item","numeric-id":1059087,"id":"Q1059087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$6D0F019E-9E6E-4F3C-A45B-4045220F227D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9072ccc8ca84abbe6603840a39a2c07e8ec058b","datavalue":{"value":{"entity-type":"item","numeric-id":1928526,"id":"Q1928526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$6283D37F-53E3-48ED-BF25-3E53819FCCB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"edda913be096c478cf2c4021961c8124f63009ce","datavalue":{"value":{"entity-type":"item","numeric-id":3099544,"id":"Q3099544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$827A5C3D-22FB-4012-A3AF-A90E30B8B605","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c920e2edbf7c9e845a24842c91b0eca208ca3860","datavalue":{"value":{"entity-type":"item","numeric-id":982621,"id":"Q982621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$24D43D78-61A8-4EFC-9607-1CFC585AD0FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"840105a3441e8d0091e38973e23744a53af29463","datavalue":{"value":{"entity-type":"item","numeric-id":2804745,"id":"Q2804745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$88E5B4D9-4855-4563-B26A-50A57C0BAD02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7de26b873a31ca9503b70a2d03a7a825d467af7b","datavalue":{"value":{"entity-type":"item","numeric-id":2991965,"id":"Q2991965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$E5EAAAD0-9FF3-4965-A569-26C8B01734A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df6120b48d6795aa0a5fc5723195f8dcc36bcbe8","datavalue":{"value":{"entity-type":"item","numeric-id":2876013,"id":"Q2876013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$6A7A549D-C723-425A-8867-CC863039875B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3c434f88ec4237cc08e14bac1e832a50ec66547","datavalue":{"value":{"entity-type":"item","numeric-id":3012590,"id":"Q3012590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$F6182563-4B18-4E68-8899-63F139208C2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c31c3e341c247f398afb437743f0535b2b4f83c4","datavalue":{"value":{"entity-type":"item","numeric-id":2227103,"id":"Q2227103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$5C558C17-41FE-4887-ADC2-ED2A7AAD2EDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ef7577bf80d2659188f77950f0e9ddddd7585af","datavalue":{"value":{"entity-type":"item","numeric-id":567002,"id":"Q567002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$BA25FB47-E0A4-4E0C-9605-017D29694183","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14eea89bd9ee9cef960b009951a4c2debeae55f6","datavalue":{"value":{"entity-type":"item","numeric-id":2680983,"id":"Q2680983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$EC24094B-F411-4648-85A3-A3E0B768AB53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75ad6c72926142f6f5bc971cfe73fd8f62855b7b","datavalue":{"value":{"entity-type":"item","numeric-id":2112653,"id":"Q2112653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6559394$AC8ED946-C337-4D7C-9B8C-040EEDC950DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d13b2fbb76bd5533a125fa19dcf703af171db743","datavalue":{"value":"10.1016/J.DAM.2024.04.027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6559394$9331ED6C-7A41-4467-A03F-A5F635765DB8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"023c67b7ae84d9864d6c7788f0f2a37ee2a64062","datavalue":{"value":{"entity-type":"item","numeric-id":2227103,"id":"Q2227103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ea209d97c928b28a53c5e3a0995e24ba9ef7e00","datavalue":{"value":{"amount":"+0.8986209034919739","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":"Q6559394$E8FEF95C-1F11-4B9B-9B55-2767D2EEE6E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21a510c7d21bb088480a75bbeb8d78df009fbd73","datavalue":{"value":{"entity-type":"item","numeric-id":3099544,"id":"Q3099544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39bcec30ba57f1fbd8a38d33d2aa71095ea598d4","datavalue":{"value":{"amount":"+0.8980703949928284","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":"Q6559394$4F46E5AB-CEE1-42C7-9145-12F74A0E16B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01ae94d810485db25ab041521d803ff9f2995e2f","datavalue":{"value":{"entity-type":"item","numeric-id":2364084,"id":"Q2364084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"79a089eb36638259165abccccf2cfed3be831ff1","datavalue":{"value":{"amount":"+0.8591687083244324","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":"Q6559394$6D0DDA87-EC3D-4FD7-9DDA-F6514F30B5DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e4bde95b57e80911fe199de667ff6f6ac809ba8","datavalue":{"value":{"entity-type":"item","numeric-id":2804745,"id":"Q2804745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"950b01b4d635d057f28b0d8b6205fd8a15263c22","datavalue":{"value":{"amount":"+0.8572608828544617","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":"Q6559394$0133DE0B-E1FB-417E-93BC-3780E6FC676A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f99c353efc6df69b901f8f48f6c53e652d1bac7","datavalue":{"value":{"entity-type":"item","numeric-id":2876013,"id":"Q2876013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"60404a56ca6cfe1210e705d035adc33b70d99d9c","datavalue":{"value":{"amount":"+0.8432455658912659","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":"Q6559394$327066DD-03CE-4EF1-AF6F-24FFB160E268","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6559394","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6559394"}}}}}