Independence in Direct-Product Graphs

Abstract

Let $\alpha (G)$ denote the independence number of a graph $G$ and let $G\times H$ be the direct product of graphs $G$ and $H$. Set $\underset{\_}{\alpha }(G\times H)=max\{\alpha (G)–|H|,\alpha (H)–|G|\}$. If $G$ is a path or a cycle and $H$ is a path or a cycle, then $\alpha (G\times H)=\underset{\_}{\alpha }(G\times H)$. Moreover, this equality holds also in the case when $G$ is a bipartite graph with a perfect matching and $H$ is a traceable graph. However, for any graph $G$ with at least one edge and for any $i\in \mathbb{N}$, there is a graph $H_c$ such that $\alpha (G\times H)>\underset{\_}{\alpha }(G\times H)+i$.