On (Kq;k)-Stable Graphs
Andrzej Żak · Journal of Graph Theory · 2012
A graph G is called -vertex stable if G contains a subgraph isomorphic to H even after removing any k of its vertices. By stab we denote the minimum size among the sizes of all -vertex stable graphs. Given an integer , we prove that, apart of some small values of k, stab. This confirms in the affirmative the conjecture of Dudek et al. [Discuss Math Graph Theory 28(1) (2008), 137–149]. Furthermore, we characterize the extremal graphs.