Realizability of Fault-Tolerant Graphs

A connected graph G is optimal-K if the connectivity kappa (G) = delta(G), where delta(G) is the minimum degree of G. It is super-kappa if every minimum vertex cut isolates a vertex. An optimal-kappa graph G is m-optimal-kappa if for any vertex set S subset of V (G) with vertical bar S vertical bar <= m, G-S is still optimal-kappa. The maximum integer of such in, denoted by O-kappa (G), is the vertex fault tolerance of G with respect to the property of optimal-kappa. The concept of vertex fault tolerance with respect to the property of super-kappa, denoted by S-kappa (G), is defined in a similar way. In a previous paper, we have proved that min{kappa(1)(G) - delta(G), delta(G) - 1} <= O-kappa (G) <= delta(G) - 1 and min{kappa(1) (G) - delta(G) - 1, delta(G) -1} <= S-kappa (G) <= delta(G) - 1. We also have S-kappa (G) <= O-kappa (G) <= delta(G) - 1. In this paper, we study the realizability problems concerning the above three bounds. By construction, we proved that for any non-negative integers a, b, c with a <= b <= c. (i) there exists a graph G such that kappa(1)(G) - delta(G) = a, O-kappa (G) = b, and delta(G) - 1 = c; (ii) there exists a graph G with kappa(1) (G) - delta(G) - 1 = a, S-kappa(G) = b, and delta(G) - 1 = c; and (iii) there exists a graph G such that S-kappa (G) = a, O-kappa (G) = b, and delta(G) - 1 = c.