Strong product of graphs
In graph theory, the strong product G ⊠ H of graphs G and H is a graph such that[1] 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'.
It is the union of the Cartesian product and the tensor product.
The strong product is also called the normal product and the AND product.[citation needed] It was first introduced by Sabidussi in 1960.[2] In that setting, the strong product is contrasted against a "weak" product, but the two are different only when applied to infinitely many factors.
For example, the king's graph, a graph whose vertices are squares of a chessboard and whose edges represent possible moves of a chess king, is a strong product of two path graphs.[3]
Care should be exercised when encountering the term strong product in the literature, since it has also been used to denote the tensor product of graphs.[4]
See also
References
- ^ 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.