## Abstract

The total domination number γ_{t}(G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex of G is adjacent to a vertex in S. Our main result of this paper is that if G is a connected graph and x_{1},x_{2},x_{3}∈V(G), then γ_{t} (G)≥1/4(d(x_{1},x_{2})+d(x _{1},x_{3})+d(x_{2},x_{3})). Furthermore if equality holds in this bound, then the multiset {d(x_{1},x _{2}),d(x_{1},x_{3}),d(x_{2},x_{3})} is equal to {2,3,3} modulo four. As a consequence of this result, we prove a conjecture on the total domination number. To state this conjecture, let B denote the set of vertices of maximum eccentricity in G and let ecc(B) denote the maximum distance in G of a vertex outside B to a vertex of B. The following conjecture is known as Graffiti.pc Conjecture #233 (http://cms.dt.uh.edu/ faculty/delavinae/research/wowII): if G is a connected graph of order at least two, then γ_{t}(G)≥2(ecc(B)+1)/3. We prove this conjecture. In fact, as a consequence of our main result stated earlier we prove the following much stronger result: if G is a connected graph of order at least two, then γ_{t}(G)≥(3ecc(B)+2)/4. We also prove that if G is a connected graph and x_{1},x_{2},x_{3},x_{4}∈V(G), then γ_{t} (G)≥1/8(d(x_{1},x_{2})+d(x _{1},x_{3})+d(x_{1},x_{4})+d(x _{2},x_{3})+d(x_{2},x_{4})+d(x _{3},x_{4})), and this result is best possible.

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

Pages (from-to) | 45-52 |

Number of pages | 8 |

Journal | Discrete Applied Mathematics |

Volume | 173 |

DOIs | |

Publication status | Published - 20 Aug 2014 |

## Keywords

- Distance
- Eccentricity
- Periphery
- Total domination number

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics