Unsolved algorithmic problems on trees (Q2508406)

The results and problems surveyed link to the two volumes on domination in graphs by \textit{T. W. Haynes} et al. [Fundamentals of domination in graphs. Pure and Applied Mathematics, Marcel Dekker. 208. New York, NY: Marcel Dekker, Inc. (1998; Zbl 0890.05002) and Domination in graphs. Advanced topics. Pure and Applied Mathematics, Marcel Dekker. 209. New York, NY: Marcel Dekker, Inc. (1998; Zbl 0883.00011)]. About 60 graph parameters are defined, some of them for the first time. The corresponding decision problems are known or conjectured to be NP-complete for graphs in general, but polynomial if restricted to trees. A list of 100 references annexes to original work.