A characterisation of universal minimal total dominating functions in trees. (English) Zbl 0824.05034

Cockayne, E. J.; Mynhardt, C. M.

Discrete Math. 141, No. 1-3, 75-84 (1995).

A total dominating function (TDF) of a graph \(G= (V, E)\) is a mapping \(f\) of \(V\) into the closed interval \([0, 1]\) of real numbers with the property that for each \(v\in V\) the sum of values of \(f\) in all vertices adjacent to \(v\) is at least 1. A TDF is called minimal (MTDF), if there exists no TDF \(g\) of \(G\) with the property that \(g(x)\leq f(x)\) for all \(x\in V\) and \(g(x_ 0)< f(x_ 0)\) at least for one \(x_ 0\in V\). A convex combination of two functions \(f\), \(g\) is a function \(h_ \lambda\) given by \(h_ \lambda(x)= \lambda f(x)+ (1- \lambda) g(x)\), where \(\lambda\) is a real number from the interval \([0,1]\). If a MTDF has the property that its convex combination with any other MTDF is also a MTDF, it is called a universal MTDF. In the paper the universal minimal total dominating functions of trees are characterized.

Reviewer: B.Zelinka (Liberec)

MSC:

05C35	Extremal problems in graph theory
05C05	Trees
05C75	Structural characterization of families of graphs

Keywords:

characterization; minimal total dominating functions; total dominating function; TDF; convex combination of two functions; universal minimal total dominating functions; trees

References:

[1]	Cockayne, E.J.; Mynhardt, C.M.; Yu, B., Universal minimal total dominating functions in graphs, Networks, 24, 83-90, (1994) · Zbl 0804.90122
[2]	E.J. Cockayne, C.M. Mynhardt and B. Yu, Total dominating functions in trees: minimality and convexity, J. Graph Theory, to appear. · Zbl 0819.05035
[3]	A. Stacey, Universal minimal total dominating functions of trees, preprint. · Zbl 0824.05036
[4]	Yu, B., Convexity of minimal total dominating functions in graphs, () · Zbl 0876.05048