Research output: Contribution to journal › Article › peer-review
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 (Formula presented.) 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.
Original language | English |
---|---|
Pages (from-to) | 666-682 |
Number of pages | 17 |
Journal | Journal of Mathematical Sciences (United States) |
Volume | 212 |
Issue number | 6 |
Early online date | 8 Jan 2016 |
DOIs | |
State | Published - 2016 |
ID: 36925181