Independence in Direct-Product Graphs.
Pranava K. Jha, Sandi Klavžar · 1998
Let α(G) denote the independence number of a graph G and let G ×H be the direct product of graphs G and H. Set α(G ×H) = max{α(G) · |H|, α(H) · |G|}. If G is a path or a cycle and H is a path or a cycle then α(G×H) = α(G×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 there is a graph H such that α(G×H)> α(G×H) + i. 1