General lower bound on the size of \((H;k)\)-stable graphs
A graph \(G\) is called \((H;k)\)-vertex stable if \(G\) contains a subgraph isomorphic to \(H\) ever 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 first (non-trivial) general lower bound for stab\((H;k)\) with regard to the order, connectivity and minimum degree of \(H\). This bound is nearly sharp for \(k=1\).
connectivity minimum degree vertex-stable graph