On dominating sets of maximal outerplanar and planar graphs

详细信息    查看全文

• 作者：Zepeng Li^a ; ^{lizepeng@pku.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Enqiang Zhu^a ; ^{zhuenqiang@pku.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Zehui Shao^b ; ^c ; ^{zshao@cdu.edu.cn" class="auth_mail" title="E-mail the corresponding author} ; Jin Xu^a ; ^{jxu@pku.edu.cn" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Dominating set ; Domination number ; Maximal planar graph ; Maximal outerplanar graph
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：10 January 2016
• 年：2016
• 卷：198
• 期：Complete
• 页码：164-169
• 全文大小：419 K

文摘

A set D⊆V(G)$D\subseteq V\left(G\right)$ of a graph G$G$ is a dominating set if every vertex v∈V(G)$v\in V\left(G\right)$ is either in D$D$ or adjacent to a vertex in D$D$. The domination number γ(G)$\gamma \left(G\right)$ of a graph G$G$ is the minimum cardinality of a dominating set of G$G$. Campos and Wakabayashi (2013) and Tokunaga (2013) proved independently that if G$G$ is an n$n$-vertex maximal outerplanar graph having t$t$ vertices of degree 2, then $\gamma \left(G\right)\le \frac{n+t}{4}$. We improve their upper bound by showing $\gamma \left(G\right)\le \frac{n+k}{4}$, where k$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 \left(G\right)\le \frac{5n}{16}$ for a Hamiltonian maximal planar graph G$G$ with n≥7$n\ge 7$ vertices.