| EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS |
| |
| 引用本文： | FANGQizhi. EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS[J]. 系统科学与复杂性, 2004, 17(4): 485-491 |
| |
| 作者姓名： | FANGQizhi |
| |
| 作者单位： | Department of Mathematics，Ocean University of China，Qingdao 266071，Shandong，China |
| |
| 基金项目： | 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.
|
| 关 键 词： | 最小全优势函数 平衡 NP难 通用MTDF 矩阵 图 |
EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS |
| |
| FANG Qizhi. EXISTENCE OF 0-1 UNIVERSAL MINIMAL TOTAL DOMINATING FUNCTIONS[J]. Journal of Systems Science and Complexity, 2004, 17(4): 485-491 |
| |
| Authors: | FANG Qizhi |
| |
| Abstract: | 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. |
| |
| Keywords: | Total dominating function (TDF) minimal total dominating function (MTDF) universal MTDF balanced NP-hard. |
| 本文献已被 CNKI 维普 等数据库收录！ |
