Basic minimal dominating functions

Abstract

A dominating function (DF) of a graph G = (V, E) is a function f : V → [0,1] such that for all v ∈ V, the sum of the function values over the closed neighbourhood of v is at least one. A DF f is called minimal (MDF) if there is no function g: V → [0,1] such that g < f and g is a DF. An MDF f is called basic (BMDF) if f cannot be expressed as a proper convex combination of two MDFs. In this paper we obtain a necessary and sufficient condition for an MDF to be a BMDF. 2000 Mathematics Subject Classification: Primary 05C 69; Secondary 05C 35.