Geodesic
The tree of decomposition of a biconnected graph
Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VI, Tome 417 (2013), pp. 86-105 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

The tree of decomposition of a $k$-connected graph by a set $\mathfrak S$ of pairwise independent $k$-vertex cutsets is defined as follows. The vertices of this tree are cutsets of $\mathfrak S$ and parts of decomposition of the graph by the set $\mathfrak S$, each cutset is adjacent to all parts that contain it. We prove, that the graph described above is a tree. The tree of decomposition of a biconnected graph is a particular case of this construction: it is the tree of decomposition of a biconnected graph by the set of all its single cutsets (i.e., $2$-vertex cutsets, that are independent with all other $2$-vertex cutsets). We show that this tree has much in common with the classic tree of blocks and cutpoints of a connected graph. With the help of the tree of decomposition of a biconnected graph we prove a planarity criterium and find some upper bounds on the chromatic number of this graph. Finally, we study the structure of critical biconnected graphs and prove that each such graph has at least four vertices of degree 2. 
@article{ZNSL_2013_417_a2,
     author = {D. V. Karpov},
     title = {The tree of decomposition of a~biconnected graph},
     journal = {Zapiski Nauchnykh Seminarov POMI},
     pages = {86--105},
     year = {2013},
     volume = {417},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a2/}
}
TY  - JOUR
AU  - D. V. Karpov
TI  - The tree of decomposition of a biconnected graph
JO  - Zapiski Nauchnykh Seminarov POMI
PY  - 2013
SP  - 86
EP  - 105
VL  - 417
UR  - http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a2/
LA  - ru
ID  - ZNSL_2013_417_a2
ER  - 
%0 Journal Article
%A D. V. Karpov
%T The tree of decomposition of a biconnected graph
%J Zapiski Nauchnykh Seminarov POMI
%D 2013
%P 86-105
%V 417
%U http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a2/
%G ru
%F ZNSL_2013_417_a2
D. V. Karpov. The tree of decomposition of a biconnected graph. Zapiski Nauchnykh Seminarov POMI, Combinatorics and graph theory. Part VI, Tome 417 (2013), pp. 86-105. http://geodesic.mathdoc.fr/item/ZNSL_2013_417_a2/

[1] S. MacLane, “A structural characterization of planar combinatorial graphs”, Duke Math. J., 3:3 (1937), 460–472 | DOI | MR | Zbl

[2] G. Chartrand, A. Kaugars, D. R. Lick, “Critically $n$-connected graphs”, Proc. Amer. Math. Soc., 32 (1972), 63–68 | MR | Zbl

[3] Y. O. Hamidoune, “On critically $h$-connected graphs”, Discr. Math., 32 (1980), 257–262 | DOI | MR | Zbl

[4] W. T. Tutte, Connectivity in graphs, Univ. Toronto Press, Toronto, 1966 | MR | Zbl

[5] W. T. Tutte, “A theory of $3$-connected graphs”, Indag. Math., 23 (1961), 441–455 | MR

[6] W. Hohberg, “The decomposition of graphs into $k$-connected components”, Discr. Math., 109 (1992), 133–145 | DOI | MR | Zbl

[7] F. Kharari, Teoriya grafov, Mir, M., 1973 | MR

[8] O. Ore, Teoriya grafov, Nauka, M., 1968 | MR

[9] D. V. Karpov, A. V. Pastor, “O strukture $k$-svyaznogo grafa”, Zap. nauchn. semin. POMI, 266, 2000, 76–106 | MR | Zbl

[10] D. V. Karpov, “Bloki v $k$-svyaznykh grafakh”, Zap. nauchn. semin. POMI, 293, 2002, 59–93 | MR | Zbl

[11] D. V. Karpov, “Razdelyayuschie mnozhestva v $k$-svyaznom grafe”, Zap. nauchn. semin. POMI, 340, 2006, 33–60 | MR | Zbl