Minimal k-Connected Graphs with Minimal Number of Vertices of Degree k
- Authors: Karpov D.V.1
-
Affiliations:
- St. Petersburg Department of the Steklov Mathematical Institute, St. Petersburg State University
- Issue: Vol 212, No 6 (2016)
- Pages: 666-682
- Section: Article
- URL: https://journal-vniispk.ru/1072-3374/article/view/237122
- DOI: https://doi.org/10.1007/s10958-016-2697-1
- ID: 237122
Cite item
Abstract
A graph is k-connected if it has at least k+1 vertices and remains connected after deleting any k−1 vertices. A k-connected graph is said to be minimal if any its subgraph obtained by deleting any edge is not k-connected. W. Mader proved that any minimal k-connected graph with n vertices has at least\( \frac{\left(k-1\right)n+2k}{2k-1} \)vertices of degree k. The main result of the present paper is that any minimal k-connected graph with minimal number of vertices of degree k is isomorphic to a graph Gk,T, where T is a tree the maximal vertex degree of which is at most k + 1. The graph Gk,Tis constructed from k disjoint copies of the tree T in the following way. If a is a vertex of T of degree j and a1, . . . , akare the corresponding vertices of the copies of T, then k + 1 − j new vertices of degree k, which are adjacent to {a1, . . . , ak}, are added. Bibliography: 10 titles.
About the authors
D. V. Karpov
St. Petersburg Department of the Steklov Mathematical Institute, St. Petersburg State University
Author for correspondence.
Email: dvk0@yandex.ru
Russian Federation, St. Petersburg
Supplementary files
