Some results on universal minimal total dominating functions (Q5942759)

The open neighbourhood \(N(v)\) of a vertex \(v\) in a graph \(G\) is the set of all vertices of \(G\) which are adjacent to \(v\). A mapping \(f\) of the vertex set \(V(G)\) of \(G\) into the closed interval \([0,1]\) on the real line is called a total dominating function on \(G\), if \(\sum_{x\in v(G)} f(x)\geq 1\) for each \(v\in V(G)\). A total dominating function \(f\) is minimal (MTDF), if for each total dominating function \(g\) on \(G\) the inequalities \(g(x)\leq f(x)\) for all \(x\in V(G)\) imply the identity \(f\equiv g\). A MTDF on \(G\) is called universal, if it has the property that its convex combinations with any other MTDF are also MTDFs. In the paper universal MTDEs are studied with the help of the concepts of redundant constraint and exceptional vertex. Conditions for a MTDF to be universal are studied in graphs (in general) and in trees. It is proved that there is a polynomial time algorithm for deciding whether a given graph has a universal MTDF, and to construct it in the affirmative case.