A. V. Pastor, “About vertices of degree $6$ of $C_3$-critical minimal $6$-connected graph”, Zap. Nauchn. Sem. POMI, 2014, Volume 427,Pages 89

About vertices of degree $6$ of $C_3$-critical minimal $6$-connected graph

A. V. Pastor^ab

^a St. Petersburg Department of V. A. Steklov Institute of Mathematics of the Russian Academy of Sciences, St. Petersburg, Russia
^b St. Petersburg State Polytechnical University, St. Petersburg, Russia

Abstract: In this paper we research $C_3$-critical minimal $6$-connected graphs, i.e. such $6$-connected graphs, that lost there $6$-connectivity when we delete any edge and in which any clique on at most $3$ verticies is contained in a $6$-cutset. We prove that more than $\frac59$ of all verticies of a such graph has degree $6$.

Key words and phrases: $k$-connectivity, minimal $k$-connected graph, $C_3$-critical $k$-connected graph.

UDC: 519.173.1

Received: 20.10.2014