On the Independence Number of the Cartesian Product of Caterpillars

Scott P.Martin1, Jeffrey S.Powell1, Douglas F.Rall1
1Furman University Greenville, SC

Abstract

By considering the order of the largest induced bipartite subgraph of \(G\), Hagauer and Klaviar [4] were able to improve the bounds first published by V. G. Vizing [6] for the independence number of the Cartesian product \(G \Box H\) for any graph \(H\). In this paper, we study maximum independent sets in \(G \Box H\) when \(G\) is a caterpillar, and derive bounds for the independence number when \(H\) is bipartite. The upper bound we produce is less than or equal to that in [4] when \(H\) is also a caterpillar, and is shown to be strictly smaller when \(H\) comes from a restricted class of caterpillars.