Edge-cuts leaving components of order at least three
type: Item
instance of: scholarly article
title: Edge-cuts leaving components of order at least three
zbMATH Open document ID: 1017.05063
DOI: 10.1016/S0012-365X(02)00385-0
author: Paul Bonsma
author: Nicola Ueffing
author: Lutz Volkmann
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: A graph \(G\) is said to be \(\lambda_p\)-edge connected if there is a set of edges whose removal breaks the graph into connected components each of cardinality at least \(p\). The minimum cardinality of such a cut, if it exists, is the order-\(p\) edge connectivity of \(G\). Under the name of extraconnectivity, this notion was studied in a series of papers [see \textit{J. Fàbrega} and \textit{M. A. Fiol}, Discrete Math. 155, 49-57 (1996; Zbl 0857.05064) and the references therein]. In the present paper the authors prove that a graph \(G\) of order \(n\geq 6\) is \(\lambda_3\)-edge connected unless it consists of a vertex incident with a number of triangles and/or paths of length at most three, with one additional single exception when \(n=6\). Then they show that \(\lambda_3 (G)\) is at most the minimum number of edges emanating from a set of three vertices which induce a connected graph. It is pointed out that a similar statement is no longer true for \(p\geq 4\).
reviewed by: Oriol Serra
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1838937
zbMATH Keywords: order-3 edge-connectivity
zbMATH Keywords: extraconnectivity
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1838937