Improving the Clark-Suen bound on the domination number of the Cartesian product of graphs

A long-standing Vizing's conjecture asserts that the domination number of the Cartesian product of two graphs is at least as large as the product of their domination numbers; one of the most significant results related to the conjecture is the bound of Clark and Suen, gamma(G square H) >= gamma(G) gamma(H)/2, where gamma stands for the domination number, and G square H is the Cartesian product of graphs G and H. In this note, we improve this bound by employing the 2-packing number rho(G) of a graph G into the formula, asserting that gamma(G square H) >= (2 gamma(G) - rho(G)) gamma (H)/3. The resulting bound is better than that of Clark and Suen whenever G is a graph with rho(G) < gamma(G)/2, and in the case G has diameter 2 reads as gamma(GQH) >= (2 gamma(G) - 1) gamma(H)/3. (C) 2017 Elsevier B.V. All rights reserved.