The graph strong product, also known as the graph AND product or graph normal product, is a graph product variously denoted ![G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H](https://txtdot.deep-swarm.xyz/proxy/img?url=https%3A%2F%2Fmathworld.wolfram.com%2Fimages%2Fequations%2FGraphStrongProduct%2FInline1.svg){kind=small}
,
(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.
See also
Graph Product, Graph Strength, Shannon Capacity
Portions of this entry contributed by Nicolas Bray
Portions of this entry contributed by Lorenzo Sauras-Altuzarra
Explore with Wolfram|Alpha
References
Alon, N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers of Its Powers." IEEE Trans. Inform. Th. 52, 2172-2176, 2006.Beineke, L. W. and Wilson, R. J. (Eds.). Topics in Algebraic Graph Theory. New York: Cambridge University Press, p. 104, 2004.Hammack, R.; Imrich, W.; and Klavžar, S. Handbook of Product Graphs, 2nd ed. Boca Raton, FL: CRC Press, 2016.
Referenced on Wolfram|Alpha
Cite this as:
Bray, Nicolas; Sauras-Altuzarra, Lorenzo; and Weisstein, Eric W. "Graph Strong Product." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GraphStrongProduct.html