Strong product of graphs


In graph theory, the strong product G ⊠ H of graphs G and H is a graph such that
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. It was first introduced by Sabidussi in 1960. 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.
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.