Total dominating functions in trees: Minimality and convexity. (English) Zbl 0819.05035

Authors’ abstract: A total dominating function (TDF) of a graph \(G= (V,E)\) is a function \(f: V\to [0, 1]\) such that for each \(v\in V\), \(\sum_{u\in N(v)} f(u)\geq 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).


05C35 Extremal problems in graph theory
05C40 Connectivity
05C05 Trees
Full Text: DOI


[1] Cockayne, Networks 24 pp 83– (1994)
[2] Masters thesis, University of Victoria (1992).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.