On small contractible subgraphs in 3-connected graphs of small average degree

DOI10.1007/S00373-007-0749-5MaRDI QIDQ2464049zbMATH OpenOpenAlexFDO

Authors Matthias Kriesell

Publication date 10 December 2007

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-007-0749-5

zbMATH Keywords

average degreeconnectivitycontractiblepartitionregular

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Connectivity (05C40) Structural characterization of families of graphs (05C75)

Review text

The author proves that there exists a smallest number \(k\), \(k>12\), such that every cubic 3-connected graph \(G\) on at least \(k\) vertices has a connected subgraph \(H\) on 5 vertices such that the graph obtained by removing the vertices of \(H\) from \(G\) is 2-connected.

Recommendations

• Contractible small subgraphs in \(k\)-connected graphs
• Contractible subgraphs in 3-connected graphs
• scientific article; zbMATH DE number 4132204
• Connected subgraphs with small degree sums in 3-connected planar graphs
• Large contractible subgraphs of a 3-connected graph
• scientific article; zbMATH DE number 4043878
• scientific article; zbMATH DE number 2108141
• Contractible subgraphs ink-connected graphs
• On 3-connected graphs with contractible edge covers of size \(k\)
• An included-minor result for 3-connected graphs with contractible edges

Cites work

• A survey on contractible edges in graphs of a prescribed vertex connectivity
• Almost all 3-connected graphs contain a contractible set of \(k\) vertices
• Contractible subgraphs in 3-connected graphs
• Contractible triples in 3-connected graphs
• scientific article; zbMATH DE number 3166039 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• On removable cycles through every edge

Cited in

(5)

• Degree sequences and the existence of k-factors
• On contractible 5-vertex subgraphs of a 3-connected graph
• Large contractible subgraphs of a 3-connected graph
• Contractible small subgraphs in \(k\)-connected graphs
• Every 3-connected graph with at least 13 vertices has a contractible set with 5 vertices

This page was built for publication: On small contractible subgraphs in 3-connected graphs of small average degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2464049)