Strong product of graphs
- the vertex set of G ⊠ H is the Cartesian product V(G) × V(H); and
- any two distinct vertices (u,u') and (v,v') are adjacent in G ⊠ H if and only if:
- u is adjacent to v and u'=v', or
- u=v and u' is adjacent to v', or
- u is adjacent to v and u' is adjacent to v'
The strong product is also called the normal product and 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.
- Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 1-56881-429-1.
- Sabidussi, G. (1960). "Graph multiplication". Math. Z. 72: 446–457. doi:10.1007/BF01162967. MR 0209177.
- Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130.
- See page 2 of Lovász, László (1979), "On the Shannon Capacity of a Graph", IEEE Transactions on Information Theory, IT-25 (1), doi:10.1109/TIT.1979.1055985.