Connectivity and tree structure in finite graphs

Link:
Autor/in:
Erscheinungsjahr:
2014
Medientyp:
Text
Schlagworte:
  • Algorithms
  • Graphic methods
  • Tree decomposition
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
  • Algorithms
  • Graphic methods
  • Tree decomposition
  • Graph In Graph Theory
  • Coloring
  • Graphic Methods
Beschreibung:
  • 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.
Lizenz:
  • info:eu-repo/semantics/restrictedAccess
Quellsystem:
Forschungsinformationssystem der UHH

Interne Metadaten
Quelldatensatz
oai:www.edit.fis.uni-hamburg.de:publications/7103692e-3589-469d-8de3-2a66dc72f9d4