On the tree number of regular graphs Original Research Article

A tree decomposition of a graph G is a family of subtrees whose sets of edges partition the set of edges of G. The minimum number of trees in a tree decomposition is the tree number of G. We show that regular graphs with maximum edge connectivity have the minimum possible tree number, whereas graphs with odd degree may have tree number arbitrarily close to its upperbound.