Computational Complexity of Weighted Integrity

\({Graph \; integrity}\), a measure of graph vulnerability, has drawn considerable attention of graph theorists in recent years. We have given a set of sufficient conditions for the weighted integrity problem to be NP-Complete for a class of graphs. As a corollary of this result, we have shown that the weighted graph integrity problem is NP-Complete on many common classes of graphs on which the unweighted integrity problem is either polynomial or of unknown complexity. We have shown that the weighted graph integrity problem is polynomial for interval graphs.