Some New Bounds and Exact Results on the Independence Number of Cartesian Product Graphs

Abstract

The independence number of Cartesian product graphs is considered. An upper bound is presented that covers all previously known upper bounds. A construction is described that produces a maximal independent set of a Cartesian product graph and turns out to be a reasonably good lower bound for the independence number. The construction defines an invariant of Cartesian product graphs that is compared with its independence number. Several exact independence numbers of products of bipartite graphs are also obtained.