Bound on \(m\)-restricted edge connectivity
type: Item
instance of: scholarly article
title: Bound on \(m\)-restricted edge connectivity
zbMATH Open document ID: 1049.05049
author: Jianping Ou
author: Fuji Zhang
published in: Acta Mathematicae Applicatae Sinica. English Series
publication date: 2004-06-22T00:00:00Z
review text: An \(m\)-restricted edge-cut is an edge-cut that separates a connected graph into a disconnected graph such that each component consists of at least \(m\) vertices. The minimum cardinality over all \(m\)-restricted edge-cuts is called the \(m\)-restricted edge-connectivity \(\lambda_m\). If \(G\) is a graph, \(X\subseteq V(G)\) and \(\overline X=V(G)-X\), then let \(G[X]\) be the subgraph induced by \(X\) and \((X,\overline X)\) be the set of edges with one end in \(X\) and the other one in \(\overline X\). Now let \[ \xi_m=\min\{| (X,\overline X)| :\,X\subset V(G),\,| X| =m,\, G[X]\text{ is connected}\}. \] The main theorem (Theorem 3.1) of this paper says: Let \(G\) be a connected \(k\)-regular graph of order at least \(2m\) that contains an \(m\)-restricted edge-cut. If the girth \(g>m/2+1\), then \(\lambda_m\leq\xi_m\). Reviewer's remark: For more information on the \(m\)-restricted edge-connetivity, see also \textit{P. Bonsma}, \textit{N. Ueffing} and \textit{L. Volkmann} [Discrete Math. 256, 431--439 (2002; Zbl 1017.05063)].
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C40
zbMATH DE Number: 2076960
zbMATH Keywords: restricted edge-connectivity
zbMATH Keywords: regular graph
MaRDI profile type: Publication
full work available at URL: s10255-003-0127-x
OpenAlex ID: W2085075037
cites work: Super Line-Connectivity Properties of Circulant Graphs
cites work: Q3097395
cites work: On computing a conditional edge-connectivity of a graph
cites work: On a kind of restricted edge connectivity of graphs
DOI: 10.1007/S10255-003-0127-X
description: scientific article; zbMATH DE number 2076960