The fully weighted toughness of a graph (Q6180647)

This paper considers graphs with a weighting on the vertices. Throughout, the authors use that each weight is nonnegative and that the total weight is positive. Since a graph with connectivity 1 is not Hamiltonian, it follows that no value of the fully weighted toughness is sufficient to guarantee Hamiltonicity. But even if one imposes a large value of connectivity, there is no threshold. Graphs in the above family need not be 1-tough even for given connectivity but can have arbitrarily large fully weighted toughness. The toughness of a graph \(G\) is defined to be the minimum value of \(|S|/k(G-S)\), where \(k(G-S)\) denotes the number of components of \(G-S\) and the minimum is taken over all cut-sets \(S\subseteq V(G)\). Here, the authors propose a version for weighted graphs that depends on the weights in both \(S\) and \(G-S\). Apart from considering bounds and basic properties, the paper is focused on the problem of assigning weights and maximizing the parameters. The authors mean that it would be interesting to gain further insight into which graphs have \(\operatorname{MFWT}(G) = \tau(G)\) and which do not. Calculations and bounds for specific families of graphs would be helpful. For algorithmic questions, one can use similar ideas to those in [\textit{M. Shi} and \textit{Z. Wei}, J. Math. 2021, Article ID 6657594, 5 p. (2021; \url{doi:10.1155/2021/6657594})], to calculate fully weighted toughness for interval graphs; but are there other classes where calculating \(\tau w(G)\) is polynomial? One has no idea of the complexity of calculating \(\operatorname{MFWT}(G)\). This concept suggests that maybe one should investigate the weighted versions of other measures of the vulnerability of a graph. The paper has interesting results and further problems.