On the tree number of regular graphs (Q1356782)

A collection of edge-disjoint subtrees of a graph \(G\) that cover all edges of \(G\) is called a tree decomposition of \(G\). The tree number of \(G\), \(\tau(G)\), is the minimum number of trees in a tree decomposition of \(G\). The paper has two main results. The first of them states that the tree number of a \(d\)-regular graph, such that \(d\) is even and the edge-connectivity of \(G\) equals \(d\), is equal to \(d/2\) (which is also equal to the arboricity of \(G\)). The second main result shows that for every odd \(d\), there is a sequence of \(d\)-regular graphs \(G_n\) each with edge-connectivity \(d\) and such that \(\tau(G_n)\geq|V(G_n)|/2d\).