## Abstract

Let G be a graph with no isolated vertex. In this paper, we study a parameter that is squeezed between arguably the two most important domination parameters, namely the domination number, γ(G), and the total domination number, ^{γt}(G). A set S of vertices in G is a semitotal dominating set of G if it is a dominating set of G and every vertex in S is within distance 2 of another vertex of S. The semitotal domination number, ^{γt2}(G), is the minimum cardinality of a semitotal dominating set of G. We observe that γ(G)≤^{γt2}(G) ≤^{γt}(G). It is known that γ(G) ≤^{α′}(G), where ^{α′}(G) denotes the matching number of G. However, the total domination number and the matching number of a graph are generally incomparable. We provide a characterization of minimal semitotal dominating sets in graphs. Using this characterization, we prove that if G is a connected graph on at least two vertices, then ^{γt2}(G)≤^{α′}(G)+1 and we characterize the graphs achieving equality in the bound.

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

Pages (from-to) | 13-18 |

Number of pages | 6 |

Journal | Discrete Mathematics |

Volume | 324 |

Issue number | 1 |

DOIs | |

Publication status | Published - 6 Jun 2014 |

## Keywords

- Domination
- Matching
- Semitotal domination
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics