15
$\begingroup$

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 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.

$\endgroup$
8
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.