Note on an extremal problem arising from the diagnosis of regularly interconnected systems diagnosis of regularly interconnected systems

Motivated by the problem of identifying the faulty units in regular interconnected systems this paper studies the combinatorial problem of the following type: for a graph G(V,E) #V=N and any integer a, what is the minimal number f(G,a) such that the removal of f(G, a) nodes results in a graph with a maximal connected component of a nodes or less. The graphs that are studied are regular (all nodes have the same degree ) or quasi-regular graphs; the main attention is paid to planar and toroidal grids. The main result is: f(G, a) * N min(l(G,b)-2)/(2b+l(G,b)-2); l(G,b) is an isoperimetric function: the lower bound on the edges that must be used to connect the nodes that must be removed to isolate a subgraph of b nodes. Using that inequality we find new and better lower bounds.