zbMATH — the first resource for mathematics

Connectivity and tree structure in finite graphs. (English) Zbl 1324.05104
Considering systems of separations in a graph \(G\) that separate every pair of a given set of vertex sets that are themselves not separated by these separations, the authors determine conditions under which such a separation system contains a nested subsystem that still separates those sets and is invariant under automorphisms of \(G\). As an application, it is shown that the \(k\)-blocks of a graph \(G\) live in distinct parts of a tree-decomposition of \(G\) of adhesion at most \(k\), whose decomposition tree is invariant under the automorphisms of \(G\). Under mild additional assumptions, these decompositions can be combined into one overall tree-decomposition that distinguishes all the \(k\)-blocks of a finite graph.

05C40 Connectivity
05C05 Trees
05C83 Graph minors
Full Text: DOI arXiv Link
[1] J. Carmesin, R. Diestel, M. Hamann and F. Hundertmark: Canonical tree-decompositions of finite graphs I. Existence and algorithms, arXiv:1305.4668, 2013. · Zbl 1327.05269
[2] J. Carmesin, R. Diestel, M. Hamann and F. Hundertmark: Canonical tree-decompositions of finite graphs II. The parts, arXiv:1305.4909, 2013.
[3] J. Carmesin, R. Diestel, M. Hamann and F. Hundertmark: \(k\)-Blocks: a connectivity invariant for graphs, arXiv:1305.4557, 2009
[4] R. Diestel: Graph Theory, Springer, 4th edition, 2010. · Zbl 1204.05001
[5] Diestel, R; Gorbunov, K Yu; Jensen, T; Thomassen, C, Highly connected sets and the excluded grid theorem, J. Combin. Theory (Series B), 75, 61-73, (1999) · Zbl 0949.05075
[6] Dunwoody, M J, Cutting up graphs, Combinatorica, 2, 15-23, (1982) · Zbl 0504.05035
[7] M. J. Dunwoody and B. Krön: Vertex cuts, arXiv:0905.0064, 2009.
[8] F. Hundertmark: Profiles. An algebraic approach to combinatorial connectivity, arXiv:1110.6207, 2011.
[9] W. Mader: Über \(n\)-fach zusammenhängende Eckenmengen in Graphen, J. Combin. Theory (Series B), 25 (1978), 74-93. · Zbl 0319.05123
[10] Reed, B A; Bailey, R A (ed.), Tree width and tangles: a new connectivity measure and some applications, (1997) · Zbl 0895.05034
[11] Robertson, N; Seymour, P D, Graph minors. X. obstructions to tree-decomposition, J. Combin. Theory (Series B), 52, 153-190, (1991) · Zbl 0764.05069
[12] W. T. Tutte: Graph Theory, Addison-Wesley, 1984. · Zbl 0554.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.