Corollary: Bounds for the Minimal Tree Decomposability

(related to Definition: Minimal Tree Decomposability)

Let \(G(V,E,\gamma)\) be a finite undirected graph. Then the minimal tree decomposability of \(G\) has the following (trivial) bounds:

\[0\le \tau(G)\le n.\]

The lower bound can be improved, if the graph \(G\) has no loops and the total number \(l\) of components, and the total number \(m_i\) of vertices with multiedges in the \(i\)-th component, \(i=1,\ldots,l\) are known to

\[\sum_{i=1}^1 \max(1,m_i) \le \tau(G)\le n.\]

In particular, if \(G\) is a forest with exactly \(l\) trees, the minimal tree decomposability can be exactly calculated as \[\tau(G)=l.\]

Proofs: 1

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




  1. Piotrowski, Andreas: Own Research, 2014