On Independence Numbers of the Cartesian Product of Graphs

Abstract

Let $G$ and $H$ be connected graphs and let $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H$ be the Cartesian product of $G$ by $H$. A lower and an upper bound for the independence number of the Cartesian product of graphs is proved for the case, where one of the factors is bipartite. Cartesian products with one factor being an odd path or an odd cycle are considered as well.

It is proved in particular that if $S_1+S_2$ is a largest 2-independent set of a graph $G$, such that $|S_2|$ is as small as possible and if $|S_2|\le n+2$, then $\alpha (G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_{2n+1})=(n+1)|S_1|+n|S_2|$. A similar result is shown for the Cartesian product with an odd cycle. It is finally proved that $\alpha (C_{2k+1}\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_{2n+1})=k(2n+1)$, extending a result of Jha and Slutzki.