Largest component and node fault tolerance for grids (Q2656897)

Summary: A graph \(G\) is called \(t\)-node fault tolerant with respect to \(H\) if \(G\) still contains a subgraph isomorphic to \(H\) after removing any \(t\) of its vertices. The least value of \(|E(G)|-|E(H)|\) among all such graphs \(G\) is denoted by \(\Delta(t,H)\). We study fault tolerance with respect to some natural architectures of a computer network, i.e. the \(d\)-dimensional toroidal grids and the hypercubes. We provide the first non-trivial lower bounds for \(\Delta(1,H)\) in these cases. For this aim we establish a general connection between the notion of fault tolerance and the size of a largest component of a graph. In particular, we give for all values of \(k\) (and \(n)\) a lower bound on the order of the largest component of any graph obtained from \(C_n\Box C_n\) via removal of \(k\) of its vertices, which is in general optimal.