×

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.

MSC:

05C40 Connectivity
05C05 Trees
05C83 Graph minors
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[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. · Zbl 1332.05134
[3] J. Carmesin, R. Diestel, M. Hamann and F. Hundertmark: k-Blocks: a connectivity invariant for graphs, arXiv:1305.4557, 2009 · Zbl 1309.05170
[4] R. Diestel: Graph Theory, Springer, 4th edition, 2010. · Zbl 1204.05001 · doi:10.1007/978-3-642-14279-6
[5] R. Diestel, K. Yu. Gorbunov, T. Jensen and C. Thomassen: Highly connected sets and the excluded grid theorem, J. Combin. Theory (Series B), 75 (1999), 61-73. · Zbl 0949.05075 · doi:10.1006/jctb.1998.1862
[6] M. J. Dunwoody: Cutting up graphs, Combinatorica, 2 (1982), 15-23. · Zbl 0504.05035 · doi:10.1007/BF02579278
[7] M. J. Dunwoody and B. Krön: Vertex cuts, arXiv:0905.0064, 2009. · Zbl 1321.05137
[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 · doi:10.1016/S0095-8956(78)80012-4
[10] Reed, B. A.; Bailey, R. A (ed.), Tree width and tangles: a new connectivity measure and some applications (1997) · Zbl 0895.05034
[11] N. Robertson and P. D. Seymour: Graph minors. X. Obstructions to tree-decomposition. J. Combin. Theory (Series B), 52 (1991), 153-190. · Zbl 0764.05069 · doi:10.1016/0095-8956(91)90061-N
[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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.