how to prove that $\alpha(C_5 \boxtimes C_5)=5$?

Question

how to prove that $\alpha(C_5 \boxtimes C_5)=5$?

$C_5$ is cycle of length 5 and $\boxtimes$ is strong product of graphs http://en.wikipedia.org/wiki/Strong_product_of_graphs

$\alpha$ is the maximum independence number of graph.

I don't know I should find the vertices or just it will be proved?thanks for helping.

Answer 1

Here's a proof (if I've understood strong product correctly) that $\alpha(C_5\boxtimes C_5)\geq5$:

  0 1 2 3 4
0 x o x x x
1 x x x o x
2 o x x x x
3 x x o x x
4 x x x x o

(circles are vertices in the independent set.)

Here's the outline of an ugly proof that $\alpha(C_5\boxtimes C_5)\leq5$:

1. WLOG put an/the vertex adjacent to the greatest number of vertices in the independent set at $\langle 2,2\rangle$.

2. This vertex can be adjacent to at most four elements of the independent set (why?). Tackle the cases where it's adjacent to 4 and 3 elt.s separately:

   2a. There's -- up to symmetry and translations of the grid -- only one way to have this element adjacent to four vertices, this independent set has four elements.

   2b. There are -- up to symmetry and translations of the grid -- only two ways to have three adjacent elements of the independent set. Both of these give independent sets with four elements.

   2c. Now that we're down to a maximum number of two, use the sum of the degrees of the elements in the independent set to show there can't be more than five. (Use the elements' degrees in $\alpha(C_5\boxtimes C_5)$, obviously, not the independent set.)