Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Minimal k-Connected Graphs with Minimal Number of Vertices of Degree k. / Karpov, D. V.
в: Journal of Mathematical Sciences (United States), Том 212, № 6, 2016, стр. 666-682.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Minimal k-Connected Graphs with Minimal Number of Vertices of Degree k
AU - Karpov, D. V.
N1 - Karpov, D.V. Minimal k-Connected Graphs with Minimal Number of Vertices of Degree k . J Math Sci 212, 666–682 (2016). https://doi.org/10.1007/s10958-016-2697-1
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Complete Bipartite Graph
KW - Simple Path
KW - Internal Vertex
KW - Common Edge
KW - Pendant Vertex
UR - http://www.scopus.com/inward/record.url?scp=84953382210&partnerID=8YFLogxK
U2 - 10.1007/s10958-016-2697-1
DO - 10.1007/s10958-016-2697-1
M3 - Article
AN - SCOPUS:84953382210
VL - 212
SP - 666
EP - 682
JO - Journal of Mathematical Sciences
JF - Journal of Mathematical Sciences
SN - 1072-3374
IS - 6
ER -
ID: 36925181