The independence number of the strong product of odd cycles (Q1379990)

The strong product \(G\times_sH\) of two graphs \(G\) and \(H\) has vertex set \(V(G)\times V(H)\) and two vertices \((x_1,y_1)\) and \((x_2,y_2)\) are connected by an edge in \(G\times_sH\) if and only if one of the following conditions holds: (i) \(x_1y_1\in E(G)\) and \(x_2= y_2\). (ii) \(x_2y_2\in E(H)\) and \(x_1=y_1\). (iii) \(x_1y_1\in E(G)\) and \(x_2y_2\in E(H)\). In the present paper, the authors investigate the independence number (i.e. the maximal cardinality of a set of pairwise non-adjacent vertices) of strong products of odd cycles. This research was inspired by a work of Shannon on the determination of the zero-error capacity of a noisy channel which turned out to base on such kind of independence numbers. The authors determine the independence number of \(C_5\times_sC_7 \times_sC_7\) \((C_\ell\) denotes a cycle of length \(\ell)\) which turns out to be 23. To obtain this number, they have developed a special software package called NISPOC (Numerical Invariants of Strong Products of Odd Cycles). Also they present lower bounds of the independence numbers for two infinite families of strong products of odd cycles.