Extra edge connectivity and isoperimetric edge connectivity
type: Item
instance of: scholarly article
title: Extra edge connectivity and isoperimetric edge connectivity
zbMATH Open document ID: 1155.05039
author: Zhao Zhang
published in: Discrete Mathematics
publication date: 2008-09-04T00:00:00Z
review text: An edge set \(S\) of a connected graph \(G\) is a \(k\)-extra edge cut, if \(G-S\) is no longer connected, and each component of \(G-S\) has at least \(k\) vertices. The cardinality of a minimum \(k\)-extra edge cut, denoted by \(\Lambda_k(G)\), is the \(k\)-extra edge connectivity of \(G\). The \(k\)-th isoperimetric edge connectivity \(\gamma_k(G)\) is defined as \[ \gamma_k(G) = \min\{\omega(U): U\subset V(G), | U| \geq k, |\overline U| \geq k\}, \] where \(\omega(U)\) is the number of edges with one end in \(U\) and the other end in \(\overline U =V \backslash U\). Write \[ \beta_k(G) = \min\{\omega(U):U \subset V(G),|U|=k\}. \] A graph \(G\) with \(\gamma_j(G) = \beta_j(G)\) (\(j = 1,\dots,k\)) is said to be \(\gamma_k\)-optimal. In this paper, we first prove that \(\Lambda_k(G) = \gamma_k(G)\) if \(G\) is a regular graph with girth \(g \geq k/2\). Then, we show that except for \(K_{3,3}\) and \(K_{4}\), a 3-regular vertex/edge transitive graph is \(\gamma_k\)-optimal if and only if its girth is at least \(k+2\). Finally, we prove that a connected d-regular edge-transitive graph with \(d \geq 6e_{k}(G)/k\) is \(\gamma_k\)-optimal, where \(e_k(G)\) is the maximum number of edges in a subgraph of \(G\) with order \(k\).
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5321328
zbMATH Keywords: Edge-connectivity
zbMATH Keywords: Extra edge-connectivity
zbMATH Keywords: Isoperimetric edge-connectivity
zbMATH Keywords: edge set
zbMATH Keywords: extra edge cut
zbMATH Keywords: cutset
zbMATH Keywords: regular graph
zbMATH Keywords: girth
zbMATH Keywords: optimal
reviewed by: Lutz Volkmann
MaRDI profile type: Publication
full work available at URL: j.disc.2007.08.066
OpenAlex ID: W1969093443
cites work: Q4398864
cites work: Q5422499
cites work: Edge-cuts leaving components of order at least three
cites work: On computing a conditional edge-connectivity of a graph
cites work: On the extraconnectivity of graphs
cites work: Q2716030
cites work: On Isoperimetric Connectivity in Vertex-Transitive Graphs
cites work: Conditional connectivity
cites work: Q4260012
cites work: Minimale \(n\)-fach kantenzusammenhängende Graphen
cites work: Optimally super-edge-connected transitive graphs
cites work: On a kind of restricted edge connectivity of graphs
cites work: Q4870157
cites work: Q4802098
cites work: Conditional edge connectivity properties, reliability comparisons and transitivity of graphs
cites work: Q4435203
cites work: On restricted edge-connectivity of graphs.
cites work: On optimally-\(\lambda^{(3)}\) transitive graphs
cites work: Q5492623
cites work: A proof of an inequality concerning \(k\)-restricted edge connectivity
DOI: 10.1016/J.DISC.2007.08.066
description: scientific article; zbMATH DE number 5321328