An improvement on Vizing's conjecture
Let gamma (G) denote the domination number of a graph G. A Roman dominating function of a graph G is a function f : V(G) -> {0,1,2} such that every vertex with 0 has a neighbor with 2. The Roman domination number gamma(R)(G) is the minimum of f (V(G)) = Sigma nu is an element of V(G) f (v) over all such functions. Let G square H denote the Cartesian product of graphs G and H. We prove that gamma(G)gamma(H) <= gamma(R) (G square H) for all simple graphs G and H, which is an improvement of gamma(G)gamma(H) <= 2 gamma (G square H) given by Clark and Suen (2000) [2], since gamma(G square H) <= gamma(R) (G square H) <= 2 gamma(G square H). (C) 2012 Elsevier B.V. All rights reserved.
vizing's conjecture domination number roman domination number