|
Zapiski Nauchnykh Seminarov POMI, 2014, Volume 427, Pages 41–65
(Mi znsl6042)
|
|
|
|
This article is cited in 2 scientific papers (total 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.
Received: 19.11.2014
Citation:
D. V. Karpov, “Minimal $k$-connected graphs with minimal number of vertices of degree $k$”, Combinatorics and graph theory. Part VII, Zap. Nauchn. Sem. POMI, 427, POMI, St. Petersburg, 2014, 41–65; J. Math. Sci. (N. Y.), 212:6 (2016), 666–682
Linking options:
https://www.mathnet.ru/eng/znsl6042 https://www.mathnet.ru/eng/znsl/v427/p41
|
Statistics & downloads: |
Abstract page: | 268 | Full-text PDF : | 67 | References: | 43 |
|