On dominating sets of maximal outerplanar and planar graphs

doi:10.1016/j.dam.2015.06.024

CORC > 北京大学 > 信息科学技术学院

	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).