Connectivity keeping edges in graphs with large minimum degree
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.
- Connectivity keeping paths in k-connected graphs
- scientific article; zbMATH DE number 5043408
- Connectivity keeping trees in k-connected graphs
- A generalization of an edge-connectivity theorem of Chartrand
- Contractible edges in \(k\)-connected graphs with minimum degree greater than or equal to \(\lfloor \frac{ 3 k - 1}{ 2} \rfloor \)
- Contractible cycles in graphs with large minimum degree
- Contractible edges in \(n\)-connected graphs with minimum degree greater than or equal to \([5n/4]\)
- Contractible triples in 3-connected graphs
- Critically n-Connected Graphs
- Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
- Distribution of contractible edges in k-connected graphs
- Eine Eigenschaft der Atome endlicher Graphen
- Generalizaions of critical connectivity of graphs
- scientific article; zbMATH DE number 3885951 (Why is no real title available?)
- scientific article; zbMATH DE number 4160775 (Why is no real title available?)
- On \(k\)-con-critically \(n\)-connected graphs
- On critically h-connected simple graphs
- On k-critical, n-connected graphs
- On multiply critically h-connected graphs
- Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs
- Degree sequences and edge connectivity
- Connectivity keeping stars or double-stars in 2-connected graphs
- Connectivity keeping trees in 2-connected graphs with girth conditions
- Connectivity keeping paths in \(k\)-connected bipartite graphs
- Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three
- Connectivity keeping caterpillars and spiders in 2-connected graphs
- Extremal infinite graph theory
- Connectivity keeping trees in 2-connected graphs
- High connectivity keeping sets in graphs and digraphs
- Connectivity keeping trees in k-connected graphs
- Connectivity keeping paths in k-connected graphs
- On Sufficient Degree Conditions for a Graph to be k-linked
- Order of a Graph with given Vertex and Edge Connectivity and Minimum Degree
- Removing vertices from \(k\)-connected graphs without losing \(k\)-connectivity
- scientific article; zbMATH DE number 1409246 (Why is no real title available?)
- Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
- Mader's conjecture for graphs with small connectivity
- Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs
- Highly connected triples and Mader's conjecture
- A note on a new result related to Chartrand, Kaugars and Lick's theorem
- Non-path results on the connectivity keeping problem
- A survey on the vertex-(edge-)k-maximal graphs and the k-vertex-(edge-)connected graphs with redundant subgraphs
- Connectivity keeping paths containing prescribed vertices in highly connected triangle-free graphs
- Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs
- Connectivity keeping paths for k-connected bipartite graphs
- Exploring redundant trees in bipartite graphs
- Making the components of a graph \(k\)-connected
This page was built for publication: Connectivity keeping edges in graphs with large minimum degree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q933682)
