摘要
文章研究了外平面图的匹配控制数.当直径为2和3时,匹配控制数皆为2或4;当直径大于3时,笔者举例说明匹配控制数可以任意大.同时,笔者也刻画了所有直径为2的外平面图.
In this paper, we prove that outerplanar graphs with diameter two and three have bounded paired domination number. This implies that the paired domination number of such graphs can be determined in polynomial time. Furthermore, we characterize all outerplanar graphs with diameter two. On the other hand, we also give examples of outerplanar graphs of diameter at least four, having arbitrarily large paired domination numbers.
出处
《新疆大学学报(自然科学版)》
CAS
北大核心
2016年第3期275-279,共5页
Journal of Xinjiang University(Natural Science Edition)
基金
supported by the Natural Science Foundation of China(11301440
11301371)
the Fujian Provincial Department of Science and Technology(2015J05017)
关键词
匹配控制
外平面图
直径
paired domination
outerplanar graphs
diameter