\((s,m)\)-radius of \(k\)-connected graphs
type: Item
instance of: scholarly article
title: \((s,m)\)-radius of \(k\)-connected graphs
zbMATH Open document ID: 1169.05018
author: Hao Li
author: Jianping Li
published in: Discrete Mathematics
publication date: 2009-04-09T00:00:00Z
review text: 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\).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 5542435
zbMATH Keywords: \((s,m)\)-radius, cycle
zbMATH Keywords: path
zbMATH Keywords: connected graph
MaRDI profile type: Publication
full work available at URL: j.disc.2007.12.014
OpenAlex ID: W1965957106
cites work: Q5422499
cites work: On the \(k\)-diameter of \(k\)-regular \(k\)-connected graphs
cites work: Matching theory
cites work: Applications of Menger's graph theorem
DOI: 10.1016/J.DISC.2007.12.014
description: scientific article; zbMATH DE number 5542435