Connectivity and tree structure in finite graphs

Details Connectivity and tree structure in finite graphs Connectivity and tree structure in finite graphs

2011-05-09

arxiv.org/abs/1105.1611v3

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Connectivity and tree structure in finite graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Connectivity and tree structure in finite graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Connectivity and tree structure in finite graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-333563