Graph Strong Product

The graph strong 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 .

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.