# Strong product of graphs

The king's graph, a strong product of two path graphs

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

• 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 GH 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.[2]

For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs.[3]

## 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

${\displaystyle \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:[4]

${\displaystyle \vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).}$

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