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, 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) 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. 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.
|Autori interni:||LUCCIO, FABRIZIO|
|Autori:||FRANCESCHINI G; LUCCIO F; PAGLI L|
|Titolo:||Dense trees: a new look at degenerate graphs|
|Anno del prodotto:||2006|
|Digital Object Identifier (DOI):||10.1016/j.jda.2005.12.008|
|Appare nelle tipologie:||1.1 Articolo in rivista|