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' .
The king's graph, a strong product of two path graphs

It is the union of the Cartesian product and the tensor product.

The strong product is also called the normal product or the AND product. 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
  1. Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 978-1-56881-429-2.
  2. Sabidussi, G. (1960). "Graph multiplication". Math. Z. 72: 446–457. doi:10.1007/BF01162967. hdl:10338.dmlcz/102459. MR 0209177.
  3. 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.
  4. 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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.