Dense trees: a new look at degenerate graphs

Dense trees are undirected graphs defined as natural extensions of trees. They are already known in the realm of graph coloring under the name of k  -degenerate graphs. For a given integer k⩾1k⩾1, a k-dense cycle is a connected graph, where the degree of each vertex is greater than k. A k  -dense forest F=(V,E)F=(V,E) is a graph without k-dense cycles as subgraphs. If F is connected, then is a k  -dense tree. 1-dense trees are standard trees. We have |E|⩽k|V|−k(k+1)/2|E|⩽k|V|−k(k+1)/2. If equality holds F is connected and is called a maximal k-dense tree. k-trees (a subfamily of triangulated graphs) are special cases of maximal k-dense trees.We review the basic theory of dense trees in the family of graphs and show their relation with k-trees. Vertex and edge connectivity is thoroughly investigated, and the role of maximal k-dense trees as “reinforced” spanning trees of arbitrary graphs is presented. Then it is shown how a k-dense forest or tree can be decomposed into a set of standard spanning trees connected through a common “root” of k vertices. All sections include efficient construction algorithms. Applications of k-dense trees in the fields of distributed systems and data structures are finally indicated.