Operations Research Transactions ›› 2010, Vol. 14 ›› Issue (1): 85-94.

• Original Articles • Previous Articles     Next Articles

Total Dominating Functions on Subclasses    of Chordal Graphs

ZHOU Li-Gang, DAN 而Fang, WANG Hai-Chao   

  • Online:2010-03-15 Published:2010-03-15

Abstract:  In this paper we show that the $k$-total domination and signed total domination problems are NP-complete on doubly chordal graphs. Also, we present an unified approach to slove 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 elemination ordering for the strongly chordal graph is given.