On $(C_n;k)$ Stable Graphs

Abstract

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$.