On \((C_n;k)\) stable graphs (Q648395)

Summary: 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; stab\((H; k)\) denotes the minimum size among the sizes of all \((H; k)\)-vertex stable graphs. In this paper we deal with \((C_n; k)\)- vertex stable graphs with minimum size. For each \(n\) we prove that stab\((C_n; 1)\) is one of only two possible values and we give the exact value for infinitely many \(n\)'s. Furthermore we establish an upper and lower bound for stab\((C_n; k)\) for \(k \geq 2\).