RUS  ENG
Full version
JOURNALS // Zapiski Nauchnykh Seminarov POMI // Archive

Zap. Nauchn. Sem. POMI, 2019 Volume 488, Pages 143–167 (Mi znsl6916)

On vertices of degree $6$ of minimally and contraction critically $6$-connected graph

A. V. Pastorab

a St. Petersburg Department of Steklov Mathematical Institute of Russian Academy of Sciences
b Peter the Great St. Petersburg Polytechnic University

Abstract: In this paper, we research vertices of degree $6$ of minimally and contraction critically $6$-connected graph, i.e. a $6$-connected graph that will loose $6$-connectivity after removing or contracting of any edge. We prove the following theorem. If $x$ and $z$ are adjacent vertices of degree $6$ of such a graph and no other vertex of degree 6 is adjacent to $x$ or $z$ then $x$ and $z$ have at least $4$ common neighbors. Moreover, in this case we give a detailed description of the neighborhood of the set $\{x,z\}$. Also, we construct an infinite series of examples of minimally and contraction critically $6$-connected graphs, for which a fraction of vertices of degree $6$ is ${11\over17}$.

Key words and phrases: $k$-connectivity, minimally $k$-connected graph, contraction critically $k$-connected graph.

UDC: 519.173.1

Received: 25.11.2019



© Steklov Math. Inst. of RAS, 2024