A new lower bound for the total domination number in graphs proving a Graffiti.pc Conjecture

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₁,x₂,x₃∈V(G), then γ_t (G)≥1/4(d(x₁,x₂)+d(x ₁,x₃)+d(x₂,x₃)). Furthermore if equality holds in this bound, then the multiset {d(x₁,x ₂),d(x₁,x₃),d(x₂,x₃)} 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₁,x₂,x₃,x₄∈V(G), then γ_t (G)≥1/8(d(x₁,x₂)+d(x ₁,x₃)+d(x₁,x₄)+d(x ₂,x₃)+d(x₂,x₄)+d(x ₃,x₄)), and this result is best possible.