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?1 k ? 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.
connectivity k-dense tree k-tree spanning tree k-dense forest k-elimination k-degenerate graph decomposition interconnection structures