The Convexity Graph of Minimal Dominating Functions of a Graph

Abstract

Let G = (V,E) be a graph. A function f : V → [0, 1] is a dominating function if ∑u∈N[v] f(u) ≥ 1 for all v ∈ V. A dominating function f is called a minimal dominating function (MDF) if any function g : V → [0, 1] with g < f is not a dominating function. If f is an MDF of G, then Pf = {v ∈V : f(v) > 0} is the positive set of f and Bf = {v ∈ V : ∑u∈N[v] f(u) = 1} is the boundary set of f. The relation  defined on the set F of all MDFs of G by fpg if Pf = Pg and Bf = Bg is an equivalence relation which partitions F into a finite number of equivalence classes X1, X2, . . . , Xt. The convexity graph C(G) of G has {X1,X2, . . . ,Xt} as its vertex set and Xi is adjacent to Xj if there exist f ∈ Xi and g ∈ Xj such that any convex combination of f and g is an MDF of G. In this paper we determine the convexity graphs of some standard graphs. We also prove that the convexity graph of any connected graph contains K₃.