A lower bound on the size of (H;1)-vertex stable graphs

A graph G is called (H;k)-vertex stable if G contains a subgraph isomorphic to H even after removing any k of its vertices. By stab(H;k) we denote the minimum size among the sizes of all (H;k)-vertex stable graphs. In this paper we present a general result concerning (H;1)-vertex stable graphs. Namely, for an arbitrary graph H we give a lower bound for stab(H;1) in terms of the order, connectivity and minimum degree of H. The bound is nearly sharp.