The Immersion Order, Forbidden Subgraphs and the Complexity of Network Integrity

Abstract

The $vertexintegrity$ of a graph $I(G)$, is given by $I(G)=\underset{V^{\prime }}{min}(|V^{\prime }|+m(G–V^{\prime }))$ where $V^{\prime }\subseteq V(G)$ and $m(G–V^{\prime })$ is the maximum order of a component of $G–V^{\prime }$. The $edgeintegrity$, $I^{\prime }(G)$, is similarly defined to be $I^{\prime }(G)=\underset{E^{\prime }}{min}(|E^{\prime }|+m(G–E^{\prime }))$. 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^{\prime }(G)\le k$ is a lower ideal in the partial ordering of graphs by immersions. The obstruction sets for $k\le 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^{\prime }(G)$ is at most $k$. For variable $k$, the problem of determining whether $I^{\prime }(G)$ is at most $k$ is shown to be NP-complete, complementing a similar previous result concerning $I(G)$.