CONVEXITY OF MINIMAL TOTAL DOMINATING FUNCTIONS IN GRAPHS

A total dominating function (TDF) of a graph G = (V, E) is a function f:V --> [0, 1] such that for each v is an element of V, the sum of f v alues over the open neighbourhood of v is at least one. Zero-one value d TDFs are precisely the characteristic functions of total dominating sets of G. We study the convexity of minimal total dominating function s. A minimal total dominating function (MTDF) f is called universal if convex combinations of f and any other MTDF are minimal. Generalizing and unifying two previous major results by Cockayne, Mynhardt and Yu in the area, we give a stronger sufficiency condition for an MTDF to b e universal. Moreover, we define a splitting operation on a graph G, w hich preserves the universality. Using the operation, we give many mor e classes of graphs having a universal MTDF. (C) 1997 John Wiley & Son s, Inc.