Connectivity keeping edges in graphs with large minimum degree
type: Item
instance of: scholarly article
title: Connectivity keeping edges in graphs with large minimum degree
zbMATH Open document ID: 1155.05037
author: Shinya Fujita
author: Ken-ichi Kawarabayashi
published in: Journal of Combinatorial Theory. Series B
publication date: 2008-07-24T00:00:00Z
review text: A classical result of \textit{G. Chartrand}, \textit{A. Kaugars}, and \textit{D.R. Lick} [Proc. Am. Math. Soc. 32, 63--68 (1972; Zbl 0211.27002)] says that every \(k\)-connected graph \(G\) with minimum degree at least \(3k/2\) contains a vertex \(v\) such that \(G-v\) is still \(k\)-connected. Inspired by this result, the authors prove that a \(k\)-connected graph \(G\) with minimum degree at least \(\lfloor 3k/2\rfloor+2\) contains an edge \(e=uv\) such that \(G-\{u,v\}\) is \(k\)-connected. Examples demonstrate that the given bound is best possible.
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 5303729
zbMATH Keywords: Connectivity
zbMATH Keywords: Minimum degree
zbMATH Keywords: Edge deletion
reviewed by: Lutz Volkmann
MaRDI profile type: Publication
full work available at URL: j.jctb.2007.11.001
OpenAlex ID: W2072217169
cites work: Critically n-Connected Graphs
cites work: Distribution of contractible edges in k-connected graphs
cites work: Contractible edges in \(n\)-connected graphs with minimum degree greater than or equal to \([5n/4]\)
cites work: Contractible cycles in graphs with large minimum degree
cites work: On critically h-connected simple graphs
cites work: On multiply critically h-connected graphs
cites work: Eine Eigenschaft der Atome endlicher Graphen
cites work: Q3220626
cites work: Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
cites work: Generalizaions of critical connectivity of graphs
cites work: On \(k\)-con-critically \(n\)-connected graphs
cites work: On k-critical, n-connected graphs
cites work: Contractible triples in 3-connected graphs
cites work: Q3487381
DOI: 10.1016/J.JCTB.2007.11.001
description: scientific article; zbMATH DE number 5303729