On minimum (K_q,k) stable graphs
Jean- Luc Fouquet, Henri Thuiller, Jean-Marie Vanherpe, A. Paweł Wojda · Discussiones Mathematicae Graph Theory · 2012
A graph G is a (K q , k) stable graph (q ≥ 3) if it contains a K q after deleting any subset of k vertices (k ≥ 0).Andrzej Żak in the paper On (K q ; k)-stable graphs, ( doi:/10.1002/jgt.21705)has proved a conjecture of Dudek, Szymański and Zwonek stating that for sufficiently large k the number of edges of a minimum (K q , k) stable graph is (2q -3)(k + 1) and that such a graph is isomorphic to sK 2q-2 + tK 2q-3 where s and t are integers such that s(q -1) + t(q -2) -1 = k.We have proved (Fouquet et al.On (K q , k) stable graphs with small k, Elektron.J. Combin.19 (2012) #P50) that for q ≥ 5 and k ≤ q 2 + 1 the graph K q+k is the unique minimum (K q , k) stable graph.In the present paper we are interested in the (K q , κ(q)) stable graphs of minimum size where κ(q) is the maximum value for which for every nonnegative integer k < κ(q) the only (K q , k) stable graph of minimum size is K q+k and by determining the exact value of κ(q).