A New Approach to Distance Stable Graphs

Abstract

Let $k$ and $\ell$ be nonnegative integers, not both zero, and $D\subseteq N–\{1\}$. A (connected) graph $G$ is defined to be $(k,\ell ,D)$-stable if for every pair $u,v$ of vertices of $G$ with $d_G(u,v)\in D$ and every set $S$ consisting of at most $k$ vertices of $V(G)–\{u,v\}$ and at most $\ell$ edges of $E(G)$, the distance between $u$ and $v$ in $G–S$ equals $d_G(u,v)$. For a positive integer $m$, let $N_{\ge m}=\{x\in N\mid x\ge m\}$. It is shown that a graph is $(k,\ell ,\{m\})$-stable if and only if it is $(k,\ell ,N_{\ge m})$-stable. Further, it is established that for every positive integer $x$, a graph is $(k+x,\ell ,\{2\})$-stable if and only if it is $(k,\ell +x,\{2\})$-stable. A generalization of $(k,\ell ,\{m\})$-stable graphs is considered. For a planar $(k,0,\{m\})$-stable graph, $m\ge 3$, a sharp bound for $k$ in terms of $m$ is derived.