Goddard, Wayne; Oellermann, Ortrud R.; Swart, Henda C. A new approach to distance stable graphs. (English) Zbl 0755.05034 J. Comb. Math. Comb. Comput. 8, 209-220 (1990). Summary: Let \(k\) and \(\ell\) be nonnegative integers not both zero and \(D\subseteq\mathbb{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 \(\mathbb{N}_{\geq m}=\{x\in\mathbb{N}\mid x\geq m\}\). It is shown that a graph is \((k,\ell,\{m\})\)-stable if and only if it is \((k,\ell,\mathbb{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. Cited in 1 Document MSC: 05C12 Distance in graphs Keywords:distance stable graphs; sharp bound PDFBibTeX XMLCite \textit{W. Goddard} et al., J. Comb. Math. Comb. Comput. 8, 209--220 (1990; Zbl 0755.05034)