\((s,m)\)-radius of \(k\)-connected graphs
Let \(G=(V,E)\) be an \(m\)-connected graph and let \(s\) be a given integer. For any \(S\subseteq V\), let \(d_m(S)\) denote the minimum integer such that, for any vertex \(y\in V\setminus S\), there exists at least \(m\) internally vertex-disjoint \((y,S)\)-paths in \(G\), each of which has length at most \(d_m(S)\). The \((s,m)\)-radius of \(G\), denoted by \(\rho_{s,m}(G)\), is defined as \(\min\{d_m(S)\mid S\subseteq V, |S|=s\}\). For \(k\)-connected \(n\)-vertex graphs \(G\) and for any given positive integer \(s\), the authors prove {\parindent=8mm \begin{itemize}\item[(1)]if \(k\geq 3\), \[ \rho_{s,3}(G)\leq\max\Big\{\frac{2n}{s},\min\big\{\frac{3n}{s},\frac{n}{k}+\frac{5n}{ks}\big\}+\frac{n}{s}\Big\}, \] and \item[(2)]if \(k\geq 4\), \[ \rho_{s,4}(G)\leq\min\Big\{\frac{3n}{s},\frac{n}{k-1}+\frac{5n}{s(k-1)}\Big\}+\frac{2n}{s}. \] \end{itemize}}The authors conjecture that \(\rho_{s,m}(G)\leq\frac{mn}{s}\) for all \(k\)-connected \(n\)-vertex graphs \(G\), where \(k\geq m\geq 2\).
scientific article; zbMATH DE number 5542435