Contractible small subgraphs in k-connected graphs

DOI10.1007/S00373-010-0930-0MaRDI QIDQ604980zbMATH OpenOpenAlexFDO

Authors Shinya Fujita, Ken-ichi Kawarabayashi

Publication date 12 November 2010

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

Full work available at URL https://doi.org/10.1007/s00373-010-0930-0

zbMATH Keywords

contractible small subgraphshighly connected graph

Mathematics Subject Classification ID

Connectivity (05C40) Structural characterization of families of graphs (05C75)

Recommendations

• A connected subgraph maintaining high connectivity
• Contractible triples in highly connected graphs
• High connectivity keeping connected subgraph
• On small contractible subgraphs in 3-connected graphs of small average degree
• Almost all 3-connected graphs contain a contractible set of \(k\) vertices

Cites work

• Contractible edges and triangles in k-connected graphs
• Contractible subgraphs in 3-connected graphs
• Contractible triples in 3-connected graphs
• How to Draw a Graph
• Nonseparating cycles inK-Connected graphs

Cited in

(5)

• Contractible subgraphs in 3-connected graphs
• On small contractible subgraphs in 3-connected graphs of small average degree
• A connected subgraph maintaining high connectivity
• High connectivity keeping connected subgraph
• On the Hardness of Eliminating Small Induced Subgraphs by Contracting Edges

This page was built for publication: Contractible small subgraphs in \(k\)-connected graphs

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