Premium
Total dominating functions in trees: Minimality and convexity
Author(s) -
Cockayne E. J.,
Mynhardt C. M.,
Yu Bo
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190109
Subject(s) - combinatorics , mathematics , convexity , graph , vertex (graph theory) , regular polygon , function (biology) , convex function , geometry , evolutionary biology , financial economics , economics , biology
A total dominating function (TDF) of a graph G = ( V, E ) is a function f : V ← [0, 1] such that for each v ϵ V, Σ uϵN(v) f(u) ≥ 1 (where N ( v ) denotes the set of neighbors of vertex v ). 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 existence in trees of a universal MTDF (i.e., an MTDF whose convex combinations with any other MTDF are also minimal). © 1995 John Wiley & Sons, Inc.