The graph strong product, also known as the graph AND product or graph normal product, is a graph product variously denoted , (Alon, and Lubetzky 2006), or (Beineke and Wilson 2004, p. 104) defined by the adjacency relations ( and ) or ( and ) or ( and ).
In other words, the graph strong product of two graphs and has vertex set and two distinct vertices and are connected iff they are adjacent or equal in each coordinate, i.e., for , either or , where is the edge set of .
Letting denote the adjacency matrix, the identity matrix, and the vertex count of , the adjacency matrix of the graph strong product of simple graphs and is given by
where denotes the Kronecker product (Hammack et al. 2016).
Graph strong products can be computed in the Wolfram Language using GraphProduct[G1, G2, "Normal"].
The graph strong product is unrelated to the graph theoretic property known as graph strength.