Dense trees: a new look at degenerate graphs |
| |
Authors: | Gianni Franceschini Fabrizio Luccio Linda Pagli |
| |
Affiliation: | aDipartimento di Informatica, Università di Pisa, Italy |
| |
Abstract: | 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 k1, 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. |
| |
Keywords: | k-dense tree k-dense forest k-elimination k-degenerate graph k-tree Spanning tree Connectivity Decomposition Interconnection structures |
本文献已被 ScienceDirect 等数据库收录! |