Strong product of graphs - Alchetron, the free social encyclopedia

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.

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.

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

Θ ( G ) = sup k α ( G k ) k = lim k → ∞ α ( G k ) k ,

László Lovász showed that Lovász theta function is multiplicative:

ϑ ( G ⊠ H ) = ϑ ( G ) ϑ ( H ) .

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

References

Strong product of graphs Wikipedia

(Text) CC BY-SA