Authors:
D.V. Karpov
Title:
Large contractible subgraphs of a 3-connected graph
Source:
Discussiones Mathematicae Graph Theory
Received 29.05.2017, Revised 18.08.2018, Accepted 20.08.2018, doi: 10.7151/dmgt.2172

Abstract:
Let m≥ 5 be a positive integer and let G be a 3-connected graph on at least 2m+1 vertices. We prove that G has a contractible set W such that m \le |W| \le 2m-4. (Recall that a set W ⊂ V(G) of a 3-connected graph G is contractible if the graph G(W) is connected and the graph G-W is 2-connected.) A particular case for m=4 is that any 3-connected graph on at least 11 vertices has a contractible set of 5 or 6 vertices.
Keywords:
connectivity, 3-connected graph, contractible subgraph

Links:
PDF