TOTAL DOMINATING FUNCTIONS IN TREES - MINIMALITY AND CONVEXITY

A total dominating function (TDF) of a graph G = (V,E) is a function f : V --> [0, 1] such that for each nu is-an-element-of V, SIGMA(u is-an -element-of N(upsilon) f(u) greater-than-or-equal-to 1 (where N(upsilo n) denotes the set of neighbors of vertex nu). Convex combinations of TDFs are also TDFs. However, convex combinations of minimal TDFs (i.e. , MTDFs) are not necessarily minimal. In this paper we discuss the exi stence in trees of a universal MTDF (i.e., an MTDF whose convex combin ations with any other MTDF are also minimal). (C) 1995 John Wiley & So ns, Inc.