Abstract
A subset S of vertices in a graph G is a dominating set if every vertex in V(G) \ S is adjacent to a vertex in S. If the graph G has no isolated vertex, then a semipaired dominating set of G is a dominating set of G with the additional property that the set S can be partitioned into two element subsets such that the vertices in each subset are at most distance two apart. The semipaired domination number γpr 2(G) is the minimum cardinality of a semipaired dominating set of G. Let G be a maximal outerplanar graph of order n with n2 vertices of degree 2. We show that if n≥ 5 , then γpr2(G)≤25n. Further, we show that if n≥ 3 , then γpr2(G)≤13(n+n2). Both bounds are shown to be tight.
Original language | English |
---|---|
Pages (from-to) | 911-926 |
Number of pages | 16 |
Journal | Journal of Combinatorial Optimization |
Volume | 38 |
Issue number | 3 |
DOIs | |
Publication status | Published - 15 Oct 2019 |
Keywords
- Maximal outerplanar graphs
- Paired-domination
- Semipaired domination number
ASJC Scopus subject areas
- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics