A degree sum condition for the existence of a contractible edge in a \(\kappa\)-connected graph

DOI10.1006/jctb.2000.2024zbMath1030.05068OpenAlexW1965493781MaRDI QIDQ1850535

Matthias Kriesell

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jctb.2000.2024

zbMATH Keywords

distancesreductionconnectivitycontractible edgedegree sum conditionavergage degree

Mathematics Subject Classification ID

Distance in graphs (05C12) Connectivity (05C40)

Related Items (23)

5-Shredders of Contraction-Critical 5-Connected Graphs ⋮ On local structure of 9- and 10-connected graphs ⋮ Vertices of degree 6 in a contraction critically 6-connected graph ⋮ The new lower bound of the number of vertices of degree 5 in contraction critical 5-connected graphs ⋮ Contractible edges in \(k\)-connected graphs with some forbidden subgraphs ⋮ Some degree and forbidden subgraph conditions for a graph to have a \(k\)-contractible edge ⋮ Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph ⋮ Removable edges in a 5-connected graph and a construction method of 5-connected graphs ⋮ Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph ⋮ Local structure of 7- and 8-connected graphs ⋮ A new degree sum condition for the existence of a contractible edge in a \(\kappa\)-connected graph ⋮ Contractible edges in 7-connected graphs ⋮ Trivially noncontractible edges in a contraction critically 5-connected graph ⋮ The number of vertices of degree 5 in a contraction-critically 5-connected graph ⋮ A local structure theorem on 5-connected graphs ⋮ The number of vertices of degree 7 in a contraction-critical 7-connected graph ⋮ Some properties of contraction-critical 5-connected graphs ⋮ Removable edges in a \(k\)-connected graph and a construction method for \(k\)-connected graphs ⋮ A constructive characterization of contraction critical 8-connected graphs with minimum degree 9 ⋮ A new lower bound on the number of trivially noncontractible edges in contraction critical 5-connected graphs ⋮ How to contract a vertex transitive 5-connected graph ⋮ Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids ⋮ A local condition for \(k\)-contractible edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjunkte Fragmente in kritisch n-fach zusammenhängenden Graphen
• Generalizaions of critical connectivity of graphs
• Contractible edges in \(n\)-connected graphs with minimum degree greater than or equal to \([5n/4\)]
• Contractible non-edges in \(3\)-connected graphs
• Contractible non-edges in triangle-free graphs
• On induced subgraphs of a block

This page was built for publication: A degree sum condition for the existence of a contractible edge in a \(\kappa\)-connected graph