Extremal P4P4-stable graphs

We call a graph Gk-stable (with respect to some graph HH) if, deleting any kk edges of GG, the remaining graph still contains HH as a subgraph. For a fixed HH, the minimum number of edges in a kk-stable graph is denoted by S(k)S(k). We prove general bounds on S(k)S(k) and compute the exact value of the function S(k)S(k) for H=P4H=P4. The main result can be applied to extremal kk-edge-Hamiltonian hypergraphs.