The independence number of the strong product of cycles (Q1125025)

The strong product of graphs \(G\) and \(H\) is the graph \(G\boxtimes H\) with vertex set \(V(G)\times V(H)\) and \(\{(x_1, x_2), (y_1, y_2)\}\in E(G\boxtimes H)\), whenever either \(x_1y_1\in E(G)\) and \(x_2= y_2\), or \(x_2y_2\in E(H)\) and \(x_1= y_1\), or \(x_1y_1\in E(G)\), \(x_2 y_2\in E(H)\). The author describes algorithms to determine the independence number of two infinite families of graphs: \(C_5\boxtimes C_7\boxtimes C_{2k+1}\) and \(C_5\boxtimes C_9\boxtimes C_{2k+1}\). Applications to the chromatic number of strong products of odd cycles and to the Shannon capacity of \(C_7\) are also discussed.