Contents

Lower Bounds for Dominating Cartesian Products

Bert L. Hartnell1, Douglas F. Rall2
1Saint Mary’s University Halifax, Nova Scotia Canada B3H 3C3
2Furman University Greenville, SC 29613 U.S.A.

Abstract

A well-known problem in domination theory is the long-standing conjecture of V.G. Vizing from 1963 (see [7]) that the domination number of the Cartesian product of two graphs is at least as large as the product of the domination numbers of the individual graphs.
Although limited progress has been made, this problem essentially remains open. The usefulness of a maximum 2-packing in one of the graphs in establishing a lower bound has been recognized for some time.
In this paper, we shall extend this approach so as to take advantage of 2-packings whose membership can be altered in a certain way. This results in an improved lower bound for graphs which have 2-packings of this type.