On $(C_n;k)$ Stable Graphs

  • Sylwia Cichacz
  • Agnieszka Görlich
  • Magorzata Zwonek
  • Andrzej Żak

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

Published
2011-10-17
Article Number
P205