## Abstract

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Let G be a connected graph of order n with minimum degree at least two and with maximum degree at least three. We define a vertex as large if it has degree more than 2 and we let ℒ be the set of all large vertices of G. Let P be any component of G-ℒ; it is a path. If |P| ≡ 0 (mod 4) and either the two ends of P are adjacent in G to the same large vertex or the two ends of P are adjacent to different, but adjacent, large vertices in G, we call P a 0-path. If |P| ≥ 5 and |P| ≡ 1 (mod 4) with the two ends of P adjacent in G to the same large vertex, we call P a 1-path. If |P| ≡ 3 (mod 4), we call P a 3-path. For i ∈ {0, 1, 3}, we denote the number of i-paths in G by p_{i}. We show that the total domination number of G is at most (n + p_{0} +P _{1} + p_{3})/2. This result generalizes a result shown in several manuscripts (see, for example, J. Graph Theory 46 (2004), 207-210) which states that if G is a graph of order n with minimum degree at least three, then the total domination of G is at most n/2. It also generalizes a result by Lam and Wei stating that if G is a graph of order n with minimum degree at least two and with no degree-2 vertex adjacent to two other degree-2 vertices, then the total domination of G is at most n/2.

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

Article number | R65 |

Journal | Electronic Journal of Combinatorics |

Volume | 14 |

Issue number | 1 R |

DOIs | |

Publication status | Published - 7 Sept 2007 |

Externally published | Yes |

## Keywords

- Bounds
- Path components
- Total domination number

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics
- Applied Mathematics