Strong product of graphs
In graph theory, the strong product G ⊠ H of graphs G and H is a graph such that
- 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.
Shannon capacity and Lovász number
He used this fact to upper bound the Shannon capacity by the Lovász number.
- See Lemma 2 and Theorem 7 in Lovász (1979).
- Imrich, Wilfried; Klavžar, Sandi; Rall, Douglas F. (2008). Graphs and their Cartesian Products. A. K. Peters. ISBN 1-56881-429-1.
- 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.
- Sabidussi, G. (1960). "Graph multiplication". Math. Z. 72: 446–457. doi:10.1007/BF01162967. MR 0209177.