## Abstract

Let G be a graph with vertex set V and no isolated vertices. A subset S⊆ V is a semipaired dominating set of G if every vertex in V\ S is adjacent to a vertex in S and 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. We show that if G is a connected graph of order n with minimum degree at least 2, then γpr2(G)≤12(n+1). Further, we show that if n≢3(mod4), then γpr2(G)≤12n, and we show that for every value of n≡3(mod4), there exists a connected graph G of order n with minimum degree at least 2 satisfying γpr2(G)=12(n+1). As a consequence of this result, we prove that every graph G of order n with minimum degree at least 3 satisfies γpr2(G)≤12n.

Original language | English |
---|---|

Pages (from-to) | 451-486 |

Number of pages | 36 |

Journal | Journal of Combinatorial Optimization |

Volume | 41 |

Issue number | 2 |

DOIs | |

Publication status | Published - Feb 2021 |

## Keywords

- Domination
- Paired domination
- Semipaired domination
- Semipaired domination number

## ASJC Scopus subject areas

- Computer Science Applications
- Discrete Mathematics and Combinatorics
- Control and Optimization
- Computational Theory and Mathematics
- Applied Mathematics