The Shields-Harary indices of vulnerability of a graph (Q5943357): Difference between revisions

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))\). The 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)]. In 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. It 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]\). Under 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. If \(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)\). A 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\}\). A 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. Finally, 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.