Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
Minimal Biconnected Graphs. / Karpov, D. V.
в: Journal of Mathematical Sciences (United States), Том 204, № 2, 2015, стр. 244-257.Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
}
TY - JOUR
T1 - Minimal Biconnected Graphs
AU - Karpov, D. V.
N1 - Karpov, D.V. Minimal Biconnected Graphs. J Math Sci 204, 244–257 (2015). https://doi.org/10.1007/s10958-014-2199-y
PY - 2015
Y1 - 2015
N2 - A biconnected graph is called minimal if it becomes not biconnected after deleting any edge. We consider minimal biconnected graphs that have minimal number of vertices of degree 2. Denote the set of all such graphs on n vertices by GM(n). It is known that a graph from GM(n) contains exactly (formula presented)vertices of degree 2. We prove that for k ≥ 1, the set GM(3k + 2) consists of all graphs of the type GT, where T is a tree on k vertices the vertex degrees of which do not exceed 3. The graph GT is constructed from two copies of the tree T : to each pair of the corresponding vertices of these two copies that have degree j in T we add 3−j new vertices of degree 2 adjacent to this pair. Graphs of the sets GM(3k) and GM(3k+1) are described with the help of graphs GT. Bibliography: 12 titles.
AB - A biconnected graph is called minimal if it becomes not biconnected after deleting any edge. We consider minimal biconnected graphs that have minimal number of vertices of degree 2. Denote the set of all such graphs on n vertices by GM(n). It is known that a graph from GM(n) contains exactly (formula presented)vertices of degree 2. We prove that for k ≥ 1, the set GM(3k + 2) consists of all graphs of the type GT, where T is a tree on k vertices the vertex degrees of which do not exceed 3. The graph GT is constructed from two copies of the tree T : to each pair of the corresponding vertices of these two copies that have degree j in T we add 3−j new vertices of degree 2 adjacent to this pair. Graphs of the sets GM(3k) and GM(3k+1) are described with the help of graphs GT. Bibliography: 12 titles.
KW - Pairwise Disjoint
KW - Terminal Part
KW - Decomposition Tree
KW - Vertex Degree
KW - Boundary Vertex
UR - http://www.scopus.com/inward/record.url?scp=84925487247&partnerID=8YFLogxK
U2 - 10.1007/s10958-014-2199-y
DO - 10.1007/s10958-014-2199-y
M3 - Article
AN - SCOPUS:84925487247
VL - 204
SP - 244
EP - 257
JO - Journal of Mathematical Sciences
JF - Journal of Mathematical Sciences
SN - 1072-3374
IS - 2
ER -
ID: 36925352