The Independence Number of the Cartesian Product of Graphs

Abstract

We study the independence number of the Cartesian product of binary trees and more general bipartite graphs. We give necessary and sufficient conditions on bipartite graphs under which certain upper and lower bounds on the independence number of the product are equal. A basic tool will be an algorithm for finding the independence number of a binary tree.