$k$-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$

Abstract

Vertex-fault-tolerance was introduced by Hayes~\cite{Hayes1976} in 1976, and since then it has been systematically studied in different aspects. In this paper we study $k$-vertex-fault-tolerant graphs for $p$ disjoint complete graphs of order $c$, i.e., graphs in which removing any $k$ vertices leaves a graph that has $p$ disjoint complete graphs of order $c$ as a subgraph. The main contribution is to describe such graphs that have the smallest possible number of edges for $k=1$, $p\ge 1$, and $c\ge 3$. Moreover, we analyze some properties of such graphs for any value of $k$.