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

Zap. Nauchn. Sem. POMI, 2014 Volume 427, Pages 41–65 (Mi znsl6042)

This article is cited in 2 papers

Minimal $k$-connected graphs with minimal number of vertices of degree $k$

D. V. Karpovab

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

Abstract: A graph is $k$-connected if it has at least $k+1$ vertices and remains connected after deleting any its $k-1$ vertices. A $k$-connected graph is called minimal, if it becomes not $k$-connected after deleting any edge. W. Mader has proved that any minimal $k$-connected graph on $n$ vertices has at least $\frac{(k-1)n+2k}{2k-1}$ vertices of degree $k$. We prove that any minimal $k$-connected graph with minimal number of vertices of degree $k$ is a graph $G_{k,T}$ for some tree $T$ with vertex degrees at most $k+1$. The graph $G_{k,T}$ is constructed from $k$ disjoint copies of the tree $T$. For any vertex $a$ of the tree $T$ we denote by $a_1,\dots,a_k$ the correspondent vertices of copies of $T$. If the vertex $a$ has degree $j$ in the tree $T$ then we add $k+1-j$ new vertices of degree $k$ which are adjacent to $\{a_1,\dots,a_k\}$.

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

UDC: 519.173.1

Received: 19.11.2014


 English version:
Journal of Mathematical Sciences (New York), 2016, 212:6, 666–682

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024