Notes on the independence number in the Cartesian product of graphs
G. Abay-Asmeron, Richard H. Hammack, C. E. Larson, David T. Taylor · Discussiones Mathematicae Graph Theory · 2011
Every connected graph G with radius r(G) and independence number (G) obeys (G) r(G). Recently the graphs for which equality holds have been classied. Here we investigate the members of this class that are Cartesian products. We show that for non-trivial graphs G and H, (G2H) = r(G2H) if and only if one factor is a complete graph on two vertices, and the other is a nontrivial complete graph. We also prove a new (polynomial computable) lower bound (G2H) 2r(G)r(H) for the independence number and we classify graphs for which equality holds. The second part of the paper concerns independence irreducibility.