×

A new approach to distance stable graphs. (English) Zbl 0755.05034

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.

MSC:

05C12 Distance in graphs
PDFBibTeX XMLCite