I that $G=(V,E,W)$ is a weighted graph with positive edge weights and a finite set of vertices $K$. Let $0\le k,M\le K$ be a fixed integer.
Is is known when $G$ admits the following type of decomposition:
- There are disjoint subsets $V_1,\dots,V_N$ of $V$ such that $\#V\setminus\cup_{n=1}^N\,V_n \le k$ and each $\# V_n \le M$
- There are subsets $E_1,\dots,E_N$ of $E$ such that each $E_n\subset V_n^2$
- For $n=1,\dots,N$, each $T_n:=(V_n,E_n,W_n)$ is tree satisfying $$ d_{T_n}(u,v) = d_G(u,v) $$ for each $u,v\in V_n$.
Here, $d_{T_n}$ and $d_G$ denote the shortest path metric on $T_n$ and on $G$, respectively.
Clearly, everything works nicely when $G$ is a forest, but are more general classes of graphs known which satisfy this property?
