Consider two graphs $G=(V,E)$ and $H=(W,F)$. For the sake of simplicity, say that both $G$ and $H$ contain all self-loops. Let $N_G(v)$ and $N_H(w)$ be the first neighborhoods of any vertex $v\in V$ (in $G$) and $w\in W$ (in $H$), respectively. Then the strong product $G\boxtimes H$ of $G$ and $H$ is a graph with set of nodes $V\times W$ in which a pair $(v,w)\in V\times W$ is adjacent to another one $(v',w')\in V \times W$ if and only if $(v,w) \in N_G(v')\times N_H(w')$.
It is easy to see that the independence number $\alpha(G\boxtimes H)$ of $G\boxtimes H$ is always larger than or equal to the product $\alpha(G)\alpha(H)$ of the independence numbers $\alpha(G)$ of $G$ and $\alpha(H)$ of $H$. This is because the Cartesian product $I\times J$ of an independent set $I$ in $G$ with an independent set $J$ in $H$ is an independent set in $G\boxtimes H$.
I assume it is not always the case that $\alpha(G\boxtimes H) = \alpha(G)\alpha(H)$ (not even up to constants) because I keep finding the upper bound $\alpha(G\boxtimes H) \le \alpha^\star(G)\alpha(H)$, where $\alpha^\star(G)$ is the fractional packing (or Rosenfeld) number of $G$, which I know can be much bigger than $\alpha(G)$.
This got me wondering:
Question: Is it possible that $\alpha(G\boxtimes H) \gg \alpha(G)\alpha(H)$?
E.g., can I find two sequences of graphs $(G_n)_{n\in\mathbb N},(H_n)_{n\in\mathbb N}$ with $\alpha(G_n)\alpha(H_n)= const$ but $\alpha(G_n\boxtimes H_n) \to \infty$ as $n\to \infty$ (where the divergence is, say, faster than logarithmic)?
Best Answer
First of all, the traditional example of a case where $\alpha(G \boxtimes H) \ne \alpha(G) \alpha(H)$ is $G = H = C_5$. We have $\alpha(C_5) = 2$ but $\alpha(C_5 \boxtimes C_5) = 5$ by choosing vertices in the following pattern:
(In this representation of $C_5 \boxtimes C_5$, you should think of the $5 \times 5$ grid as a torus - both pairs of opposite sides wrap around - with vertices adjacent iff they are a king's move apart.)
As you saw in my answer to your previous question, even finding graphs with $\alpha^*(G) \gg \alpha(G)$ is not entirely straightforward, and due to the upper bound you cite, that's a prerequisite to finding an example here.
However, we can check that the final example from that post also works here. (Probably the others do, too.) Let $G$ and $H$ both be the $k$-fold iterated blow-up of $C_5$: as before,
Then $G$ has $5^k$ vertices and $\alpha(G) = 2^k$. However, we can check that $\alpha(G \boxtimes G)$ is at least $5^k$ (out of $25^k$ vertices).
Essentially, we can take the independent set in $\alpha(C_5 \boxtimes C_5)$ and apply that idea in $\alpha(G \boxtimes G)$. This gives us $5$ sets $S_1, S_2, S_3, S_4, S_5$ of $25^{k-1}$ vertices each, with no edges between $S_i, S_j$ when $i \ne j$. The subgraph of $G \boxtimes G$ induced by each $S_i$ is just the previous iteration of this construction, and we can induct to find an independent subset of each $S_i$ with $5^{k-1}$ vertices: $5^k$ vertices total.