## Abstract

Let G = (V, E) be a graph. A set S ⊆ V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V {minus 45 degree rule} S. The restrained domination number of G, denoted by γ_{r} (G), is the minimum cardinality of an RDS of G. A set S ⊆ V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γ_{t} (G), is the minimum cardinality of a TDS of G. Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ ≥ 2, then it is shown that γ_{r} (G) ≤ n - Δ, and we characterize the connected graphs with δ ≥ 2 achieving this bound that have no 3-cycle as well as those connected graphs with δ ≥ 2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n ≥ 3 and Δ ≤ n - 2, then γ_{t} (G) ≤ n - Δ. We further characterize the connected graphs G of order n ≥ 3 with Δ ≤ n - 2 that have no 3-cycle and achieve γ_{t} (G) = n - Δ.

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

Pages (from-to) | 2845-2852 |

Number of pages | 8 |

Journal | Discrete Mathematics |

Volume | 307 |

Issue number | 22 |

DOIs | |

Publication status | Published - 28 Oct 2007 |

Externally published | Yes |

## Keywords

- Restrained domination
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics