Application of Upper and Lower Bounds for the Domination Number to Vizing’s Conjecture

Abstract

Vizing conjectured that \(\gamma(G)\gamma(H) \leq \gamma(G \Box H)\) for all graphs \(G\) and \(H\), where \(\gamma(G)\) denotes the domination number of \(G\) and \(G \Box H\) is the Cartesian product of \(G\) and \(H\). We prove that if \(G\) and \(H\) are \(\delta\)-regular, then, with only a few possible exceptions, Vizing’s conjecture holds. We also prove that if \(\delta(G), \Delta(G), \delta(H)\), and \(\Delta(H)\) are in a certain range, then Vizing’s conjecture holds. In particular, we show that for graphs of order at most \(n\) with minimum degrees at least \(\sqrt{n} \ln n\), the conjecture holds.