A generalization of the block decomposition for k-connected graphs

  • Jared León USP


The decomposition of a connected graph by the set of its cut-vertices, sometimes called the "block decomposition" or "block tree" of a graph, is a well known and basic concept in graph theory. This decomposition, however, does not provide any meaningful information when applied to a $k$-connected graph for $k \geq 2$. There has been a number of attempts to generalize the construction of the block decomposition of a graph for the case of $k$-connected graphs. In this work, we present an outline of one such attempt by Karpov. We also present some applications of this decomposition to the study of planarity, the chromatic number, and critically $2$-connected graphs.

Palavras-chave: block decomposition, block tree, $k$-connectivity


Hamidoune, Y. O. (1980). On critically h-connected simple graphs. Discrete Math., 32(3):257–262.

Karpov, D. V. (2013). The decomposition tree of a two-connected graph. Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI), 417(VI):86–105.

Mac Lane, S. (1937). A structural characterization of planar combinatorial graphs. Duke Math. J., 3(3):460–472.

Tutte, W. T. (1966). Connectivity in graphs. Mathematical Expositions, No. 15. University of Toronto Press, Toronto, Ont.; Oxford University Press, London.
Como Citar

Selecione um Formato
LEÓN, Jared. A generalization of the block decomposition for k-connected graphs. In: ENCONTRO DE TEORIA DA COMPUTAÇÃO (ETC), 7. , 2022, Niterói. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2022 . p. 85-88. ISSN 2595-6116. DOI: https://doi.org/10.5753/etc.2022.223106.