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 \(\underline{\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) = \underline{\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 ) > \underline{\alpha}(G \times H ) + i\).