Strong product of graphs

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

  • 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 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.

Shannon capacity and Lovász number[edit]

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

 = \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:[1]

 \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[edit]


  1. ^ See Lemma 2 and Theorem 7 in Lovász (1979).