# Strong product of graphs

In graph theory, the strong product GH of graphs G and H is a graph such that

• the vertex set of GH is the Cartesian product V(G) × V(H); and
• any two distinct vertices (u,u') and (v,v') are adjacent in G × H if and only if:
• u is adjacent to v and u'=v', or
• u=v and u' is adjacent to v', or
• u is adjacent to v and u' is adjacent to v'

The strong product is also called the normal product and AND product. It was first introduced by Sabidussi in 1960.

## Shannon capacity and Lovász number

The Shannon capacity of a graph is defined from the independence number of its strong products with itself, by the formula

$\Theta(G) = \sup_k \sqrt[k]{\alpha(G^k)} = \lim_{k \rightarrow \infty} \sqrt[k]{\alpha(G^k)},$

László Lovász showed that Lovász theta function is multiplicative:[1]

$\vartheta(G \boxtimes H) = \vartheta(G) \vartheta(H).$

He used this fact to upper bound the Shannon capacity by the Lovász number.

## Notes

1. ^ See Lemma 2 and Theorem 7 in Lovász (1979).