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

The total domination number γt(G)γt(G) of a graph GG is the minimum cardinality of a set SS of vertices so that every vertex of GG is adjacent to a vertex in SS. Our main result of this paper is that if GG is a connected graph and x1,x2,x3∈V(G)x1,x2,x3∈V(G), then γt(G)≥14(d(x1,x2)+d(x1,x3)+d(x2,x3)). Furthermore if equality holds in this bound, then the multiset {d(x1,x2),d(x1,x3),d(x2,x3)}{d(x1,x2),d(x1,x3),d(x2,x3)} is equal to {2,3,3}{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 BB denote the set of vertices of maximum eccentricity in GG and let ecc(B) denote the maximum distance in GG of a vertex outside BB to a vertex of BB. The following conjecture is known as Graffiti.pc Conjecture #233 (http://cms.dt.uh.edu/faculty/delavinae/research/wowII): if GG 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 GG is a connected graph of order at least two, then γt(G)≥(3ecc(B)+2)/4. We also prove that if GG is a connected graph and x1,x2,x3,x4∈V(G)x1,x2,x3,x4∈V(G), then γt(G)≥18(d(x1,x2)+d(x1,x3)+d(x1,x4)+d(x2,x3)+d(x2,x4)+d(x3,x4)), and this result is best possible.