{"entities":{"Q5943357":{"pageid":8120159,"ns":120,"title":"Item:Q5943357","lastrevid":93522545,"modified":"2026-06-05T04:32:41Z","type":"item","id":"Q5943357","labels":{"en":{"language":"en","value":"The Shields-Harary indices of vulnerability of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1643027"}},"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":"Q5943357$3BAFB0D7-EDA1-4B2E-93AD-611BE519BB20","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"28a7c204962c5ba36b4d882d870e51e6b5cdc11e","datavalue":{"value":{"text":"The Shields-Harary indices of vulnerability of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5943357$2DB1CA56-6B12-422B-8B5B-1FEC6A17F115","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71c4fd1d8ebd2709887c020bc20743b24cffd2b7","datavalue":{"value":"1001.05071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943357$C64DEB3D-5B8F-4DEC-8FD6-692172D22787","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e24d35f2a878b80fbe47c70a723ba09aec74d33d","datavalue":{"value":"10.1016/S0895-7177(01)00062-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943357$18BD8E8F-01F6-4B0E-A47C-023812A3769D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"06d35deff844ad14009ec831196ab8a1bd18feeb","datavalue":{"value":{"entity-type":"item","numeric-id":293362,"id":"Q293362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$1E72061C-1511-4ECC-8350-E7C42E4EDCF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"92bdc64dc7afbf45da7bcbf303db3ae3648f9486","datavalue":{"value":{"entity-type":"item","numeric-id":749690,"id":"Q749690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$8FE60A4E-B5BE-472B-B81A-4D9D8CD31485","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b010567da0e068295e34b824b5eafea5ffd18ef1","datavalue":{"value":{"entity-type":"item","numeric-id":166953,"id":"Q166953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$D7B13994-BB0F-4EB0-809D-31C7873A1FF8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3bcaad5c4e66075ad98d9ce0731bcafdcfd4146f","datavalue":{"value":{"time":"+2002-11-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5943357$F358AD59-3243-48AF-A83D-A8A45AEB10CC","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6dbc03ded8dc8f343dbb91f0750fa930e4a14011","datavalue":{"value":{"entity-type":"item","numeric-id":205838,"id":"Q205838"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$E560EE7C-CAE4-4374-8A1C-0F708077B844","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943357$81DEBC28-D3CC-4D8C-A0F3-082A3899D283","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6005c7e2202ec2d3eb7c6aaa36159a9cc552f2e","datavalue":{"value":"1643027","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5943357$D5635F05-C6C6-4FEA-AD2B-542B7A6B7E37","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943357$4B7CE43C-AEAF-47D5-95EA-64FBCD03B940","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"254e8bda37ae244e28a5239ce72ca072c9968b10","datavalue":{"value":"Shields-Harary number","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943357$5516698B-A136-4592-B91B-7E70AB23E75C","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":"Q5943357$856DD351-2B02-4E0D-95B7-FDD7AB56A09A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea7b712ffa0cb92c8f763aa0708ea1127d5069fe","datavalue":{"value":{"entity-type":"item","numeric-id":4145718,"id":"Q4145718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$35E8BF76-F419-46F4-97EF-C4C7D533FB90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$F0ACF1D2-7447-4769-9DAC-3883622D8232","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1139bcdffc77ac56e16ee90bc6a8d6d3135e16","datavalue":{"value":{"entity-type":"item","numeric-id":4028479,"id":"Q4028479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$E4BDEB9B-DA7E-457C-8E6A-306C0F6532BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3dd4a49c6131bdd1666e58db88a7a020e6dc3347","datavalue":{"value":{"entity-type":"item","numeric-id":1891927,"id":"Q1891927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5943357$AD71C322-247C-49BF-80D0-18ACEEE578CD","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"81109424f4e683121e267762bce67423fcd5d1d2","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph, \\(I\\subset [0,\\infty)\\) be an interval, \\(f:I\\to [0,\\infty)\\) be a nonincreasing function. For a function \\(g: V\\to I\\), a set \\(S\\subset V\\) is called \\(g\\)-admissible, if \\(\\sum_ {v\\in V(H)} g(v)\\leq 1\\) holds for each component \\(H\\) of \\(G-S\\). Similarly, \\(S\\) is called strictly \\(g\\)-admissible, if the preceding inequality is strict for each \\(H\\). The Shields-Harary number of \\(G\\) is defined by \\(\\text{SH}(G,f)= \\sup_g \\min_{Sg\\text{-admissible}}\\sum_{v\\in S} f(g(v))\\). NEWLINENEWLINENEWLINEThe Shields-Harary number measures a certain kind of fortifiability of graphs: it is the minimum cost incurred by removing a subset \\(S\\) of the nodes in such a way that the remaining components have small cumulative weight \\(g\\). For \\(f(x)=1/x\\) and the path \\(P_n\\) of \\(n\\) nodes, the assertion \\(\\text{SH}(P_n,f)\\leq n\\) is equivalent to a conjecture by Shields which has been proved by \\textit{S. H. Schanuel} [Proc. Am. Math. Soc. 65, 185-186 (1977; Zbl 0368.05007)].NEWLINENEWLINENEWLINEIn the present paper, the authors study the quantity SH and some related indices: \\(\\overline{\\text{SH}}(G,f)\\) is defined in the same way as SH, but ``\\(g\\)-admissible'' is replaced by ``strictly \\(g\\)-admissible''. If the supremum is taken over all constant functions \\(g: V\\to I\\), the corresponding quantities are called \\(\\text{SH}_0\\) and \\(\\overline{\\text{SH}}_0\\), respectively.NEWLINENEWLINENEWLINEIt is proved that \\(\\text{SH}(G,f)=\\overline{\\text{SH}}(G,f)\\) and \\(\\text{SH}_0(G,f)=\\overline{\\text{SH}}_0(G,f)\\) if \\(1\\) is in the interior of the interval \\(I\\) and if \\(f\\) is continuous from the right at every point of \\(I\\cap[0,1]\\).NEWLINENEWLINENEWLINEUnder suitable conditions, the supremum in the ``strict'' quantities is actually achieved; whereas under some other conditions, the supremum in the other quantities is not a maximum.NEWLINENEWLINENEWLINEIf \\(1\\) is in the interior of \\(I\\) and \\(f\\) is continuous from the right at each point of \\(I\\cap [0,1]\\), then for each \\(g:V\\to I\\) there is a set \\(S\\subset V\\) satisfying \\(\\sum_{v\\in V(H)} g(v)<1\\) for each component \\(H\\) of \\(G-S\\), and \\(\\sum_{v\\in S}f(g(v))\\leq \\text{SH}(G,f)\\).NEWLINENEWLINENEWLINEA further result shows that---under suitable conditions on \\(I\\) and \\(f\\)---for the constant functions \\(g\\), the quantities \\(\\text{SH}_0\\) and \\(\\overline{\\text{SH}}_0\\) are achieved by constant assignments \\(1/k\\), \\(k\\in\\{1,\\dots, n\\}\\).NEWLINENEWLINENEWLINEA set \\(S\\) is called minimally \\(g\\)-admissible if it is \\(g\\)-admissible and \\(\\sum_{v\\in S} f(g(v))\\) is minimum among all such sums over \\(g\\)-admissible sets of nodes. For a subset \\(S\\) of \\(V\\), let \\(F(S)\\) be the set of all \\(g:V\\to I\\) such that \\(S\\) is minimally \\(g\\)-admissible. Then it is proved that \\(\\text{SH}(G,f)=\\max_{S\\subseteq V} \\sup_{g\\in F(S)} \\sum_{v\\in S} f(g(v))\\). Similar results hold for the other indices.NEWLINENEWLINENEWLINEFinally, bounds for some of the indices for the following graphs are given: the complete graph on \\(n\\) nodes, the star with \\(n\\) nodes, the path with \\(n\\) nodes and the cycle with \\(n\\) nodes.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5943357$1DBDAF16-594A-4ACD-86F7-8D3346430135","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc40198a9ab5b059ada7bc18abe111522af05652","datavalue":{"value":{"entity-type":"item","numeric-id":2462353,"id":"Q2462353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0099bcaf4fb4a3ba0e4816886fb8a3c3bd8936f","datavalue":{"value":{"amount":"+0.8240301609039307","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":"Q5943357$81EACD90-15D0-4BC1-AE1C-D2A6C225F7A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9d28a596f1d83a80ce0c60a1659c52034cdfa738","datavalue":{"value":{"entity-type":"item","numeric-id":1415232,"id":"Q1415232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f851630a3e863612f304f3d11a60c796449d63cb","datavalue":{"value":{"amount":"+0.8013669848442078","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":"Q5943357$44B05730-345C-4711-BCE3-4E4069B97D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"991af74e1974fa366675f5a3e4074506ee71d92b","datavalue":{"value":{"entity-type":"item","numeric-id":4028479,"id":"Q4028479"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a907ce410e4700e107df22da44731a6f81ea58a0","datavalue":{"value":{"amount":"+0.8001704216003418","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":"Q5943357$4BC5B0BC-DFEF-4CF5-B528-2B90EDE1A860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"103385e3df4c9e040999cda82369fb2ef73ea8c8","datavalue":{"value":{"entity-type":"item","numeric-id":3691699,"id":"Q3691699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a907ce410e4700e107df22da44731a6f81ea58a0","datavalue":{"value":{"amount":"+0.8001704216003418","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":"Q5943357$F62AAA1F-E0F4-477D-A739-2DEEEF4C0FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7752c6bddd33d0ff0b29c877f2ce85b80f3e8a7b","datavalue":{"value":{"entity-type":"item","numeric-id":2716639,"id":"Q2716639"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c89d3d36a73e6e3889f2b9dc6a46d055a25933e","datavalue":{"value":{"amount":"+0.7988526821136475","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":"Q5943357$D9D44117-2B7D-4A1E-A819-25B05AABD872","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The Shields-Harary indices of vulnerability of a graph","badges":[]}}}}}