# Strong product of 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
• distinct vertices (u,u' ) and (v,v' ) are adjacent in GH if and only if:
• u = v and u' is adjacent to v' , or
• u' = v' and u is adjacent to v, or
• u is adjacent to v and u' is adjacent to v' .
The king's graph, a strong product of two path graphs

It is the union of the Cartesian product and the tensor product.

The strong product is also called the normal product or the AND product.[citation needed] It was first introduced by Sabidussi in 1960.[2] In that setting, the strong product is contrasted against a weak product, but the two are different only when applied to infinitely many factors.

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]

Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.[4]