Higher edge-connectivities and tree decompositions in regular graphs (Q1972147): Difference between revisions

A tree decomposition of a graph \(G\) is a family of subtrees whose edge sets partition the edge set of \(G\). The arboricity, \(a(G)\), is a trivial lower bound of \(\tau(G)\), the minimum number of trees in a tree decomposition. In the paper it is proved that \(a(G)=\tau(G)\) for all regular graphs of order \(n\) and degree \(d\geq \lfloor n/2\rfloor\). This bound is best possible. The proof uses higher edge-connectivities, which also provide sufficient conditions for \(a(G)=\tau(G)\) when \(d>\sqrt n\) and \(G\) is a hamiltonian graph.