EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS  

作　　者：FANGQizhi 

机构地区：[1]epartmentofMathematics,OceanUniversityofChina,Qingdao266071,Shandong,China

出　　处：《Journal of Systems Science & Complexity》2004年第4期485-491,共7页系统科学与复杂性学报（英文版）

基　　金：This research is supported by the National Natural Science Foundation of China (No. 10371114).

摘　　要：In this paper, we study the existence of 0-1 universal minimal total dominating functions in a graph. We establish a formulation of linear inequalities to characterize universal minimal total dominating functions and show that for a kind of graphs whose adjacent matrices are balanced, the existence of universal minimal total dominating functions coincides with that of 0-1 ones. It is also proved that for general graphs, the problem of testing the existence of 0-1 universal minimal total dominating functions is NP-hard.

关 键 词：total dominating function (TDF) minimal total dominating function (MTDF) universal mtdf BALANCED NP-HARD 

分 类 号：O157.5[理学—数学]