## Abstract

The k-restricted total domination number of a graph G is the smallest integer t_{k} such that given any subset U of k vertices of G, there exists a total dominating set of G of cardinality at most t_{k} containing U. Hence, the k-restricted total domination number of a graph G measures how many vertices are necessary to totally dominate a graph if an arbitrary set of k vertices are specified to be in the set. When k = 0, the k-restricted total domination number is the total domination number. For 1 ≤ k ≤ n, we show that t_{k} ≤ 4(n + k)/7 for all connected graphs of order n and minimum degree at least two and we characterize the graphs achieving equality. These results extend earlier results of the author (J. Graph Theory 35 (2000), 21-45). Using these results we show that if G is a connected graph of order n with the sum of the degrees of any two adjacent vertices at least four, then γ_{t}(G) ≤ 4n/7 unless G ∈ {C _{3}, C_{5}, C_{6}, C_{10}}.

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

Pages (from-to) | 65-98 |

Number of pages | 34 |

Journal | Ars Combinatoria |

Volume | 90 |

Publication status | Published - Jan 2009 |

Externally published | Yes |

## Keywords

- Bounds
- Minimum degree two
- Total restricted domination

## ASJC Scopus subject areas

- General Mathematics