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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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