Graph Strong Product

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, G·H (Alon, and Lubetzky 2006), or G*H (Beineke and Wilson 2004, p. 104) defined by the adjacency relations (g=g^' and hadjh^') or (gadjg^' and h=h^') or (gadjg^' and hadjh^').

In other words, the graph strong product of two graphs G_1 and G_2 has vertex set V(G_1)×V(G_2) and two distinct vertices (v_1,v_2) and (u_1,u_2) are connected iff they are adjacent or equal in each coordinate, i.e., for i in {1,2}, either v_i=u_i or v_iu_i in E(G_i), where E(G) is the edge set of G.

Letting A(G) denote the adjacency matrix, I_n the n×n identity matrix, and |V(G)| the vertex count of G, the adjacency matrix of the graph strong product of simple graphs G and H is given by

 A(G square H)=A(G) tensor I_(|V(H)|)+I_(|V(G)|) tensor A(H)+A(G) tensor A(H),

where  tensor 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


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

Graph Strong Product

Cite this as:

Bray, Nicolas; Sauras-Altuzarra, Lorenzo; and Weisstein, Eric W. "Graph Strong Product." From MathWorld--A Wolfram Web Resource.

Subject classifications