# Strong product of graphs

(Redirected from Strong graph product)
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[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[4] been used to denote the tensor product of graphs.