Санкт-Петербургское отделение Математического института им. В.А.Стеклова РАН

ПРЕПРИНТ 15/2017

LARGE CONTRACTIBLE SUBGRAPHS OF A 3-CONNECTED GRAPH

This preprint was accepted December 26, 2017

ABSTRACT:
 Let  $m\ge 5$  be a positive integer and   $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.   

Д. В. Карпов

Большие стягиваемые подграфы трёхсвязного графа

АННОТАЦИЯ:
 Пусть $m\ge 5$ --- натуральное число, а    $G$  --- трёхсвязный граф с хотя бы  $2m+1$  вершиной. Доказано, что   $G$ имеет стягиваемое множество   $W$, удовлетворяющее условию  $m \le |W| \le 2m-4$. (Напомним, что множество  $W \subset V(G)$ вершин трёхсвязного графа $G$ называется стягиваемым, если граф   $G(W)$ связен, а граф  $G-W$ двусвязен.)  В частности, доказано, что любой трёхсвязный граф с  хотя бы 11 вершинами имеет стягиваемое множество из 5 или 6 вершин.