### Connectivity and tree structure in finite graphs

### Abstract

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 conditionsunder 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 treedecomposition of G of adhesion at most k, whose decomposition tree is invariant under the automorphisms of G. This extends recent work of Dunwoody and Kron 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.

### Más información

Título según WOS: | Connectivity and tree structure in finite graphs |

Título según SCOPUS: | Connectivity and tree structure in finite graphs |

Título de la Revista: | COMBINATORICA |

Volumen: | 34 |

Número: | 1 |

Editorial: | Springer |

Fecha de publicación: | 2014 |

Página de inicio: | 11 |

Página final: | 46 |

Idioma: | English |

URL: | http://link.springer.com/10.1007/s00493-014-2898-5 |

DOI: |
10.1007/s00493-014-2898-5 |

Notas: | ISI, SCOPUS |