On the extraconnectivity of graphs
type: Item
instance of: scholarly article
title: On the extraconnectivity of graphs
zbMATH Open document ID: 0857.05064
DOI: 10.1016/0012-365X(94)00369-T
author: J. Fàbrega
author: Miquel Angel Fiol
published in: Discrete Mathematics
publication date: 1997-03-06T00:00:00Z
review text: The authors extend their results on \(n\)-extraconnectivities \(\kappa(n)\) and \(\lambda(n)\) of a connected graph \(G\) with minimum degree \(\delta\), \(n\geq0\) (see [Discrete Math. 125, No. 1-3, 169-176 (1994; Zbl 0796.05058)] and [Discrete Math. 127, No. 1-9, 163-170 (1994; Zbl 0797.05058)]) (only minimum separators \(S\) are considered for which every component of \(G-S\) has more than \(n\) vertices). The authors establish sufficient conditions for \(G\) to attain the upper bound \((n+1)\delta-2n\) for \(\kappa(n)\) and \(\lambda(n)\). For example, if the girth \(g\) of \(G\) is odd and \(n\) is even then \(\lambda(n)\) is optimal whenever the diameter \(D\leq g-1-n\).
reviewed by: Ján Plesník
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C12
zbMATH DE Number: 932525
zbMATH Keywords: extraconnectivity
zbMATH Keywords: vertex connectivity
zbMATH Keywords: edge connectivity
MaRDI profile type: Publication
cites work: Circulants and their connectivities
cites work: Strongly geodetic graphs
cites work: Q3818315
cites work: Maximally connected digraphs
cites work: Extraconnectivity of graphs with large girth
cites work: Q3490015
cites work: Conditional connectivity
cites work: Q4041603
cites work: Sufficient conditions for maximally connected dense graphs
full work available at URL: 0012-365x(94)00369-t
OpenAlex ID: W1971967319
description: scientific article; zbMATH DE number 932525