Convexity of minimal dominating functions of trees: A survey

A dominating function for a graph is a function from its vertex set into the unit interval so that the sum of function values, taken over the closed neighbourhood of each vertex, is at least one. Although convex combinations of minimal dominating functions (MDFs) are themselves dominating, they are not always minimal. A universal MDF of a graph is a MDF g such that any convex combination of g with any other MDF of the graph, is minimal. This paper surveys recent results concerning convex combinations of MDFs and universal MDFs of trees. Two new theorems on the existence of certain types of MDFs of trees are established and a new class of trees without universal MDFs is presented. 1991 Mathematics Subject Classification. 05C99.