◀ ▲ ▶Branches / Graph-theory / Definition: Graph Decomposable Into `\(k\)` Trees

Definition: Graph Decomposable Into \(k\) Trees

Let \(G(V,E,\gamma)\) be a finite undirected graph \(G\) is said to be decomposable into \(k\) trees, if there exist \(k\) subsets of vertices \(V_1,\ldots,V_k\) with the following properties:

• The subgraphs induced by the vertices \(V_i\), i.e. the graphs \(G[V_i]\), are all trees.
• The \(V_i\) partition the vertices of \(G\), i.e.
  • \(V=V_1\cup\ldots\cup V_k\)
  • \(V_i\cap V_j=\emptyset\) for \(i=1,\ldots,k\), \(j=1,\ldots,k\), \(i\neq j\), and
  • \(V_i\neq\emptyset\) for \(i=1,\ldots,k\).

A given partition \(V_1,\ldots,V_k\) with these properties is called a tree decomposition of order \(k\). Please note that a graph can have different tree decompositions of the same order.

Table of Contents

1. Definition: Minimal Tree Decomposability

Mentioned in:

Definitions: 1
Proofs: 2 3 4

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Piotrowski, Andreas: Own Research, 2014