Connectivity and tree structure in finite graphs

Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein

Research output: Contribution to journalArticlepeer-review

23 Citations (Scopus)
111 Downloads (Pure)


Considering systems of separations in a graph that separate every pair of a given set of vertex sets that are themselves not separated by these separations, we determine conditions under which such a separation system contains a nested subsystem that still separates those sets and is invariant under the automorphisms of the graph. As an application, we show that the $k$-blocks -- the maximal vertex sets that cannot be separated by at most $k$ vertices -- of a graph $G$ live in distinct parts of a suitable tree-decomposition of $G$ of adhesion at most $k$, whose decomposition tree is invariant under the automorphisms of $G$. This extends recent work of Dunwoody and Kr\"on and, like theirs, generalizes a similar theorem of Tutte for $k=2$. Under mild additional assumptions, which are necessary, our decompositions can be combined into one overall tree-decomposition that distinguishes, for all $k$ simultaneously, all the $k$-blocks of a finite graph.
Original languageEnglish
Pages (from-to)11-46
Issue number1
Early online date30 Jan 2014
Publication statusPublished - 1 Feb 2014

Bibliographical note

31 pages


  • math.CO
  • 05C40, 05C05, 05C83
  • G.2.2


Dive into the research topics of 'Connectivity and tree structure in finite graphs'. Together they form a unique fingerprint.

Cite this