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

作者：Henning Michael A^*; Yeo Anders

来源：Discrete Applied Mathematics, 2014, 173: 45-52.

DOI：10.1016/j.dam.2014.03.013

• Total domination number
• Distance
• Eccentricity
• Periphery

The total domination number gamma(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 epsilon V (G), then gamma t (G) >= (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(xi, x2), d(xi, x3), d(x2, x3)} 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/wowll): if G is a connected graph of order at least two, then gamma 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 gamma 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) epsilon V (G), then gamma t(G) >= 1/8(d(x(1), x(2)) +(d(x(1), x3) + 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.

• 出版日期2014-8-20