- the vertex set of G ⊠ H is the Cartesian product V(G) × V(H); and
- distinct vertices (u,u' ) and (v,v' ) are adjacent in G ⊠ H if and only if:
- u = v and u' is adjacent to 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 or the 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 978-1-56881-429-2.
- Sabidussi, G. (1960). "Graph multiplication". Math. Z. 72: 446–457. doi:10.1007/BF01162967. hdl:10338.dmlcz/102459. 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): 1–7, doi:10.1109/TIT.1979.1055985.