Strong product of graphs

From Wikipedia, the free encyclopedia
  (Redirected from Strong graph product)
Jump to: navigation, search
The king's graph, a strong product of two path graphs

In graph theory, the strong product GH of graphs G and H is a graph such that[1]

  • the vertex set of GH is the Cartesian product V(G) × V(H); and
  • any two distinct vertices (u,u') and (v,v') are adjacent in GH 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[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[4] been used to denote the tensor product of graphs.

See also[edit]

References[edit]

  1. ^ Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Product, A. K. Peters, ISBN 1-56881-429-1 .
  2. ^ Sabidussi, G. (1960). "Graph multiplication". Math. Z. 72: 446–457. doi:10.1007/BF01162967. 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), doi:10.1109/TIT.1979.1055985 .