A New Approach to Distance Stable Graphs

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}_{\geq m} = \{x \in {N} \mid x \geq m\}\). It is shown that a graph is \((k, \ell, \{m\})\)-stable if and only if it is \((k, \ell, {N}_{\geq 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 \geq 3\), a sharp bound for \(k\) in terms of \(m\) is derived.