DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

D.V. Karpov

Title:

Large contractible subgraphs of a 3-connected graph

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-05-29, Revised: 2018-08-18, Accepted: 2018-08-20, https://doi.org/10.7151/dmgt.2172

Abstract:

Let $m\ge 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 \subset 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

PDF
Close