Abstract

Vertex-fault-tolerance was introduced by Hayes in 1976, and since then it has been systematically studied in different aspects. In this paper, we study graphs of order cp + k that are k-vertex-fault-tolerant 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. In this paper, we analyze some properties of such graphs for any value of k. The main contribution is to describe such graphs that have the smallest possible number of edges for k = 1, p >= 1, and c >= 3.