## Abstract

In this paper, we continue the study of total restrained domination in graphs, a concept introduced by Telle and Proskurowksi (Algorithms for vertex partitioning problems on partial k-trees, SIAM J. Discrete Math. 10 (1997) 529-550) as a vertex partitioning problem. A set S of vertices in a graph G = (V, E) is a total restrained dominating set of G if every vertex is adjacent to a vertex in S and every vertex of V {minus 45 degree rule} S is adjacent to a vertex in V {minus 45 degree rule} S. The minimum cardinality of a total restrained dominating set of G is the total restrained domination number of G, denoted by γ_{tr} (G). Let G be a connected graph of order n with minimum degree at least 2 and with maximum degree Δ where Δ ≤ n - 2. We prove that if n ≥ 4, then γ_{tr} (G) ≤ n - frac(Δ, 2) - 1 and this bound is sharp. If we restrict G to a bipartite graph with Δ ≥ 3, then we improve this bound by showing that γ_{tr} (G) ≤ n - frac(2, 3) Δ - frac(2, 9) sqrt(3 Δ - 8) - frac(7, 9) and that this bound is sharp.

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

Pages (from-to) | 1909-1920 |

Number of pages | 12 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 10 |

DOIs | |

Publication status | Published - 28 May 2008 |

Externally published | Yes |

## Keywords

- Bounds
- Maximum degree
- Total restrained domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics