On dominating sets of maximal outerplanar and planar graphs | |
Li, Zepeng ; Zhu, Enqiang ; Shao, Zehui ; Xu, Jin | |
刊名 | DISCRETE APPLIED MATHEMATICS
![]() |
2016 | |
关键词 | Dominating set Domination number Maximal planar graph Maximal outerplanar graph SMALL-DIAMETER |
DOI | 10.1016/j.dam.2015.06.024 |
英文摘要 | A set D subset of V(G) of a graph G is a dominating set if every vertex v is an element of V(G) is either in D or adjacent to a vertex in D. The domination number gamma (G) of a graph G is the minimum cardinality of a dominating set of G. Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G is an n-vertex maximal outerplanar graph having t vertices of degree 2, then gamma (G) <= n+t/4. We improve their upper bound by showing gamma (G) <= n+k/4 where k is the number of pairs of consecutive 2-degree vertices with distance at least 3 on the outer cycle. Moreover, we prove that gamma (G) <= 5n/12 for a Hamiltonian maximal planar graph G with n >= 7 vertices. (C) 2015 Elsevier B.V. All rights reserved.; 973 Program of China [2013CB329600]; National Natural Science Foundation of China [61309015]; National Natural Science Foundation of China Special Equipment [61127005]; SCI(E); EI; ARTICLE; lizepeng@pku.edu.cn; zhuenqiang@pku.edu.cn; zshao@cdu.edu.cn; jxu@pku.edu.cn; 164-169; 198 |
语种 | 中文 |
内容类型 | 期刊论文 |
源URL | [http://ir.pku.edu.cn/handle/20.500.11897/437835] ![]() |
专题 | 信息科学技术学院 |
推荐引用方式 GB/T 7714 | Li, Zepeng,Zhu, Enqiang,Shao, Zehui,et al. On dominating sets of maximal outerplanar and planar graphs[J]. DISCRETE APPLIED MATHEMATICS,2016. |
APA | Li, Zepeng,Zhu, Enqiang,Shao, Zehui,&Xu, Jin.(2016).On dominating sets of maximal outerplanar and planar graphs.DISCRETE APPLIED MATHEMATICS. |
MLA | Li, Zepeng,et al."On dominating sets of maximal outerplanar and planar graphs".DISCRETE APPLIED MATHEMATICS (2016). |
个性服务 |
查看访问统计 |
相关权益政策 |
暂无数据 |
收藏/分享 |
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。
修改评论