×

Total dominating functions on subclasses of chordal graphs. (Chinese. English summary) Zbl 1240.05238

Summary: In this paper, we show that the \(k\)-total domination and the signed total domination problems are NP-complete on doubly chordal graphs. Also, we present an unified approach to solve the signed total domination, minus total domination, \(k\)-total domination and \(\{k\}\)-total domination problems on a strongly chordal graph in linear-time, if the strong elimination ordering for the strongly chordal graph is given.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C22 Signed and weighted graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite