Some results on Vizing’s conjecture and related problems

The well-known conjecture of Vizing on the domination number of Cartesian product graphs claims that for any two graphs GG and HH, γ(G□H)≥γ(G)γ(H). We disprove its variations on independent domination number and Barcalkin–German number, i.e. Conjectures 9.6 and 9.2 from the recent survey Brešar et al. (2012) [4]. We also give some extensions of the double-projection argument of Clark and Suen (2000) [8], showing that their result can be improved in the case of bounded-degree graphs. Similarly, for rainbow domination number we show for every k≥1k≥1 that γrk(G□H)≥kk+1γ(G)γ(H), which is closely related to Question 9.9 from the same survey. We also prove that the minimum possible counterexample to Vizing’s conjecture cannot have two neighboring vertices of degree two.