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”.


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


Zbl 0804.90122
Full Text: DOI