Further Results on Independence in Direct-Product Graphs

For a graph \(G\), let \(\alpha(G)\) and \(\tau(G)\) denote the independence number of \(G\) and the matching number of \(G\), respectively. Further, let \(G \times H\) denote the direct product (also known as Kronecker product, cardinal product, tensor product, categorical product, and graph conjunction) of graphs \(G\) and \(H\). It is known that \(\alpha(G \times H) \geq \max\{\alpha(G)-|H|, \alpha(H)-|G|\} =: \underline{\alpha}(G \times H)\) and that \(\tau(G \times H) \geq 2.\tau(G).\tau(H) =: \underline{\tau}(G \times H)\). It is shown that an equality/inequality between \(\alpha\) and \(\underline{\alpha}\) is independent of an equality/inequality between \(\tau\) and \(\underline{\tau}\). Further, several results are presented on the existence of a complete matching in each of the two connected components of the direct product of two bipartite graphs. Additional results include an upper bound on \(\alpha(G \times H)\) that is achievable in certain cases.