<p>The following recent paper seems to be related to your question:</p>

<p>Connectivity and tree structure in finite graphs<br>
Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein</p>

<p><a href="http://arxiv.org/abs/1105.1611">http://arxiv.org/abs/1105.1611</a></p>

CC BY-SA 3.0
2012-04-06T05:23:23.697Z
2012-04-06T05:23:23.697Z
Daniel Marx
<p>A connected graph can be decomposed into its biconnected components. This <strong>block cutpoint tree</strong> is unique. Similarly, biconnected graphs can be decomposed into triconnected components. The corresponding <strong><a href="http://en.wikipedia.org/wiki/SPQR_tree" rel="nofollow noreferrer">SPQR tree</a></strong> describes all the 2-vertex cuts in the graph and is uniquely determined from its graph.</p>

<p>This process does not generalize to higher connectivity. For example, given a triconnected graph $G$, there can be multiple "trees" describing all the 3-vertex cuts of $G$.</p>

<blockquote>
  <p>Are there special classes of graphs such that $k$-connected graphs (in these classes) can be decomposed <strong>uniquely</strong> into their $k+1$-connected components.</p>
</blockquote>

<p>Note that my question is slightly different from <a href="https://cstheory.stackexchange.com/questions/8627/are-there-nice-generalizations-of-spqr-trees-to-k-connected-components-for-k3">this question</a>.</p>

<graph-theory><co.combinatorics>
Decomposing k-connected graphs into (k+1)-connected components
Shiva Kintali
# Decomposing k-connected graphs into (k+1)-connected components

(Asked by: username_0 on 2012-04-06)

A connected graph can be decomposed into its biconnected components. This **block cutpoint tree** is unique. Similarly, biconnected graphs can be decomposed into triconnected components. The corresponding **[SPQR tree](http://en.wikipedia.org/wiki/SPQR_tree)** describes all the 2-vertex cuts in the graph and is uniquely determined from its graph.

This process does not generalize to higher connectivity. For example, given a triconnected graph $G$, there can be multiple "trees" describing all the 3-vertex cuts of $G$.

> Are there special classes of graphs such that $k$-connected graphs (in these classes) can be decomposed **uniquely** into their $k+1$-connected components.

Note that my question is slightly different from [this question](https://cstheory.stackexchange.com/questions/8627/are-there-nice-generalizations-of-spqr-trees-to-k-connected-components-for-k3).

**Tags:** graph-theory, co.combinatorics


---

## 1 answers

### Answer by username_1 on 2012-04-06. Score: 8

The following recent paper seems to be related to your question:

Connectivity and tree structure in finite graphs  
Johannes Carmesin, Reinhard Diestel, Fabian Hundertmark, Maya Stein

<http://arxiv.org/abs/1105.1611>


---

