On $(C_n;k)$ Stable Graphs

Citations Over TimeTop 22% of 2011 papers

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

Related Papers

• → New Lower Bounds for Two Multicolor Vertex Folkman Numbers(2011)3 cited
• A Lower Bound on Minus Domination Number of a Graph(2010)
• → r-Dynamic Chromatic Number of Graphs(2014)
• → On conditional connectivity of the Cartesian product of cycles(2020)