## Convexity of minimal total dominating functions in graphs.(English)Zbl 0876.05048

For an ordinary graph $$G=(V,E)$$, a function $$f:V\to \{0,1\}$$ is a total dominating function if, for every $$v\in V$$, $$\sum f(x)$$ taken over the neighbours $$x$$ of $$v$$ is $$\geq 1$$; these functions are the characteristic functions of total dominating sets of vertices. A minimal total dominating function (MTDF) $$f$$ is universal if any convex combination of $$f$$ with any minimal total dominating function is also a minimal total dominating function. “Generalizing and unifying” results of E. J. Cockayne, C. M. Mynhardt and the author [Universal minimal total dominating functions in graphs, Networks 24, No. 2, 83-90 (1994; Zbl 0804.90122)], “we give a stronger sufficiency condition for an MTDF to be universal.” The author investigates the effect of the operation of replacing a vertex by several vertices having the same adjacencies, and observes that this operation preserves universality. “Using the operation we give many more classes of graphs having a universal MTDF”.

### MSC:

 05C35 Extremal problems in graph theory 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

### Keywords:

total dominating function; total dominating sets

Zbl 0804.90122
Full Text: