Research output: Contribution to journal › Article › peer-review
The Tree of Cuts and Minimal k-Connected Graphs. / Karpov, D. V.
In: Journal of Mathematical Sciences (United States), Vol. 212, No. 6, 2016, p. 654-665.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - The Tree of Cuts and Minimal k-Connected Graphs
AU - Karpov, D. V.
N1 - Karpov, D.V. The Tree of Cuts and Minimal k-Connected Graphs. J Math Sci 212, 654–665 (2016). https://doi.org/10.1007/s10958-016-2696-2
PY - 2016
Y1 - 2016
N2 - A cut of a k-connected graph G is a k-element cutset of it, which contains at least one edge. The tree of cuts of a set[MediaObject not available: see fulltext.], consisting of pairwise independent cuts of a k-connected graph, is defined in the following way. Its vertices are the cuts of the set[MediaObject not available: see fulltext.]and the parts of the decomposition of G induced by these cuts. A part A is adjacent to a cut S if and only if A contains all the vertices of S and exactly one end of each edge of S. It is proved that the defined graph is a tree, some properties of which are similar to the corresponding properties of the classic tree of blocks and cutpoints. In the second part of the paper, the tree of cuts is used to study minimal k-connected graphs for k ≤ 5. Bibliography: 11 titles.
AB - A cut of a k-connected graph G is a k-element cutset of it, which contains at least one edge. The tree of cuts of a set[MediaObject not available: see fulltext.], consisting of pairwise independent cuts of a k-connected graph, is defined in the following way. Its vertices are the cuts of the set[MediaObject not available: see fulltext.]and the parts of the decomposition of G induced by these cuts. A part A is adjacent to a cut S if and only if A contains all the vertices of S and exactly one end of each edge of S. It is proved that the defined graph is a tree, some properties of which are similar to the corresponding properties of the classic tree of blocks and cutpoints. In the second part of the paper, the tree of cuts is used to study minimal k-connected graphs for k ≤ 5. Bibliography: 11 titles.
KW - Bipartite Graph
KW - Common Edge
KW - Distinct Edge
KW - Mutual Disposition
KW - Minimal Part
UR - http://www.scopus.com/inward/record.url?scp=84953390108&partnerID=8YFLogxK
U2 - 10.1007/s10958-016-2696-2
DO - 10.1007/s10958-016-2696-2
M3 - Article
AN - SCOPUS:84953390108
VL - 212
SP - 654
EP - 665
JO - Journal of Mathematical Sciences
JF - Journal of Mathematical Sciences
SN - 1072-3374
IS - 6
ER -
ID: 36925287