Vizing-like Conjecture for the Upper Domination of Cartesian Products of Graphs – The Proof

  • Boštjan Brešar

Abstract

In this note we prove the following conjecture of Nowakowski and Rall: For arbitrary graphs $G$ and $H$ the upper domination number of the Cartesian product $G \,\square \, H$ is at least the product of their upper domination numbers, in symbols: $\Gamma(G \,\square \, H)\ge \Gamma(G)\Gamma(H).$

Published
2005-07-19
Article Number
N12