Vertex fault tolerance of optimal-κ graphs and super-κ graphs

A connected graph G is optimal-κ if κ(G)=δ(G). It is super-κ if every minimum vertex cut isolates a vertex. An optimal-κ graph G is m-optimal-κ if for any vertex set S⊆V(G) with |S|⩽m, G−S is still optimal-κ. We define the vertex fault tolerance with respect to optimal-κ, denoted by Oκ(G), as the maximum integer m such that G is m-optimal-κ. The concept of vertex fault tolerance with respect to super-κ, denoted by Sκ(G), is defined in a similar way. In this paper, we show that min{κ1(G)−δ(G),δ(G)−1}⩽Oκ(G)⩽δ(G)−1 and min{κ1(G)−δ(G)−1,δ(G)−1}⩽Sκ(G)⩽δ(G)−1, where κ1(G) is the 1-extra connectivity of G. Furthermore, when the graph is triangle free, more refined lower bound can be derived for Oκ(G).