## Abstract

A set S of vertices in a graph G is a total dominating set (TDS) of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a TDS of G is the total domination number of G, denoted by γ_{t} (G). A graph is claw-free if it does not contain K_{1, 3} as an induced subgraph. It is known [M.A. Henning, Graphs with large total domination number, J. Graph Theory 35(1) (2000) 21-45] that if G is a connected graph of order n with minimum degree at least two and G ∉ { C_{3}, C_{5}, C_{6}, C_{10} }, then γ_{t} (G) ≤ 4 n / 7. In this paper, we show that this upper bound can be improved if G is restricted to be a claw-free graph. We show that every connected claw-free graph G of order n and minimum degree at least two satisfies γ_{t} (G) ≤ (n + 2) / 2 and we characterize those graphs for which γ_{t} (G) = ⌊ (n + 2) / 2 ⌋.

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

Pages (from-to) | 3213-3219 |

Number of pages | 7 |

Journal | Discrete Mathematics |

Volume | 308 |

Issue number | 15 |

DOIs | |

Publication status | Published - 6 Aug 2008 |

Externally published | Yes |

## Keywords

- Bounds
- Claw-free graphs
- Total domination

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics