zbMATH — the first resource for mathematics

Dense trees: a new look at degenerate graphs. (English) Zbl 1103.05085
A \(k\)-dense forest (tree) is a (connected) graph of which each subgraph contains a vertex of degree at most \(k\). That is, the \(1\)-dense trees are exactly the trees, and all partial \(k\)-trees are \(k\)-dense forests, see H. L. Bodlaender [Theor. Comput. Sci. 209, 1–45 (1998; Zbl 0912.68148)]. \(k\)-dense trees were studied in connection with first-fit colouring by G. Szekeres and H. S. Wilf [J. Comb. Theory 4, 1–3 (1967; Zbl 0171.44901)] and D. W. Matula [SIAM Rev. 10, 481–482 (1968)], and also by D. R. Lick and A. T. White [Can. J. Math. 22, 1082–1096 (1970; Zbl 0202.23502)], who called them \(k\)-degenerate graphs, and by E. C. Freuder [J. Assoc. Comput. Mach. 29, 24–32 (1982; Zbl 0477.68063)]. Here the focus is on maximal \(k\)-dense trees, their relation to \(k\)-trees, and the decomposition of \(k\)-dense trees into \(k\)-spanning trees.
05C85 Graph algorithms (graph-theoretic aspects)
05C05 Trees
05C35 Extremal problems in graph theory
Full Text: DOI
[1] Arbib, C.; Flammini, M.; Nardelli, E., How to survive while visiting a graph, Discrete appl. math., 99, 279-293, (2000) · Zbl 0940.05062
[2] Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth, Theoret. comput. sci., 209, 1-45, (1998) · Zbl 0912.68148
[3] Diestel, R., Graph theory, (2000), Springer-Verlag New York · Zbl 0945.05002
[4] F. Flores Pacheco, G. Franceschini, F. Luccio, L. Pagli, Decomposition of k-dense, in: Proc. Distributed Data and Structures 3, Carleton Scientific, Ottawa, 2001, pp. 11-23
[5] G. Franceschini, Dense tree: una generalizzazione del concetto di albero, Master’s Thesis, University of Pisa (2000)
[6] Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063
[7] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman San Francisco, CA · Zbl 0411.68039
[8] Kloks, T., Treewidth. computations and approximations, Lecture notes in computer science, vol. 842, (1994), Springer-Verlag Berlin · Zbl 0825.68144
[9] Lick, D.; White, A., k-degenerate graphs, Can. J. math., 22, 1082-1096, (1970) · Zbl 0202.23502
[10] F. Luccio, A. Mesa, L. Pagli, A distributed tree data structure, in: Proc. 1st Internat. Symp. on Advanced Distributed Systems (ISADS2000), Guadalajara, Mexico, 2000, pp. 1-6
[11] F. Luccio, L. Pagli, Dense trees: a new structure for interconnection, in: Proc. Distributed Data and Structures 2, Carleton Scientific, Ottawa, 2000, pp. 56-72
[12] Matula, D.W., A min – max theorem for graphs with applications to graph coloring, SIAM rev., 10, 481-482, (1968)
[13] Nardelli, E.; Proietti, G.; Widmaer, P., Swapping a failing edge of a single source shortest path tree is good and fast, Algorithmica, 35, 56-74, (2003) · Zbl 1026.68102
[14] Peterson, L.L.; Davie, B.S., Computer networks: A systems approach, (2003), Morgan Kaufmann San Francisco, CA
[15] Szekeres, G.; Wilf, H.S., An inequality for the chromatic number of a graph, J. combin. theory, 4, 1-3, (1968) · Zbl 0171.44901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.