外平面图的全控制数  

Total Domination Number of Outerplanar Graphs

作　　者：庄蔚[1] 吴晓霞[2] ZHUANG Wei WU Xiao-xia(School of Applied Mathematcis, Xiamen University of Technology, Xiamen, Fujian 361024, China School of Mathematics and Statistics, Minnan Normal University, Zhangzhou, Fujian 363000, China)

机构地区：[1]厦门理工学院应用数学学院,福建厦门361024 [2]闽南师范大学数学与统计学院,福建漳州363000

出　　处：《闽南师范大学学报（自然科学版）》2016年第2期9-12,共4页Journal of Minnan Normal University：Natural Science

基　　金：国家自然科学基金(11301440;11301371);福建省自然科学基金(2015J05017)

摘　　要：Cockayne等人于1980年首次引入了全控制的概念.该概念在计算机网络等领域有着广泛的应用背景.因此在最近十几年,全控制这个领域被广泛的研究.本文研究了外平面图的全控制数.当直径为2和3时,作者分别给出了两种情况下外平面图的全控制数的上确界和下确界;当直径大于3时,作者举例说明全控制数可以任意大.Continue the study of total domination in graphs first introduced by Cockayne et al. in 1980 and which is now very well studied, this paper prove that outerplanar graphs with diameter two and three have bounded total domination number. This implies that the total domination number of such graphs can be determined in polynomial time. On the other hand, we also give examples of outerplanar graphs of diameter at least four, having arbitrarily large total domination numbers.

关 键 词：全控制 外平面图 直径 

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