Strong product of graphs

The king's graph, a strong product of two path 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
• 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.^[2]

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]

Shannon capacity and Lovász number

The Shannon capacity of a graph is defined from the independence number of its strong products with itself, by the formula

$\Theta (G)=\sup _{k}{\sqrt[ {k}]{\alpha (G^{k})}}=\lim _{{k\rightarrow \infty }}{\sqrt[ {k}]{\alpha (G^{k})}},$

László Lovász showed that Lovász theta function is multiplicative:^[4]

$\vartheta (G\boxtimes H)=\vartheta (G)\vartheta (H).$

He used this fact to upper bound the Shannon capacity by the Lovász number.

See also

• Graph product
• Cartesian product of graphs
• Tensor product of graphs

References

1. Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008), Graphs and their Cartesian Products, 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 Lemma 2 and Theorem 7 in 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.