Menu
The \({vertex \; integrity}\) of a graph \(I(G)\), is given by \(I(G) = \min_{V’} (|V’| + m(G – V’))\) where \(V’ \subseteq V(G)\) and \(m(G – V’)\) is the maximum order of a component of \(G – V’\). The \({edge \; integrity}\), \(I'(G)\), is similarly defined to be \(I'(G) = \min_{E’} (|E’| + m(G – E’))\). Both of these are measures of the resistance of networks to disruption. It is shown that for each positive integer \(k\), the family of finite graphs \(G\) with \(I'(G) \leq k\) is a lower ideal in the partial ordering of graphs by immersions. The obstruction sets for \(k\leq 4\) are determined and it is shown that the obstructions for arbitrary \(k\) are computable. For every fixed positive integer \(k\), it is decidable in time \(O(n)\) for an arbitrary graph \(G\) of order \(n\) whether \(I(G)\) is at most \(k\), and also whether \(I'(G)\) is at most \(k\). For variable \(k\), the problem of determining whether \(I'(G)\) is at most \(k\) is shown to be NP-complete, complementing a similar previous result concerning \(I(G)\).