Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871501 | Discrete Applied Mathematics | 2018 | 7 Pages |
Abstract
A subset S of vertices in a graph G is a secure dominating set of G if S is a dominating set of G and, for each vertex uââS, there is a vertex vâS such that uv is an edge and (Sâ{v})âª{u} is also a dominating set of G. We show that if G is a maximal outerplane graph of n vertices, then G has a secure dominating set of size at most â3nâ7â. Moreover, if a maximal outerplane graph G has no internal triangles, it has a secure dominating set of size at most ânâ3â. Finally, we show that any secure dominating set of a maximal outerplane graph without internal triangles has more than nâ4 vertices.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Toru Araki, Issei Yumoto,