Tensor product of graphs

From Wikipedia, the free encyclopedia

The tensor product of graphs.

In graph theory, the tensor 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 vertices (u,u') and (v,v') are adjacent in G × H if and only if u' is adjacent with v' and u is adjacent with v.

The tensor product is also called the direct product, categorical product, cardinal product, or Kronecker product. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica (1912). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs (Weichsel 1962).

1 Examples
2 Properties
3 References
4 External links

[edit] Examples

The double cover of a complete graph is a complete bipartite graph: K₂ × K_n = K_n,n.
The double cover of the Petersen graph is the Desargues graph: K₂ × G(5,2) = G(10,3).
The tensor product of a complete graph K_n with itself is the complement of a Rook's graph. Its vertices can be placed in an n by n grid, so that each vertex is adjacent to the the vertices that are not in the same row or column of the grid.

[edit] Properties

The tensor product is the category-theoretic product in the category of graphs and graph homomorphisms. That is, there is a homomorphism from G × H to G and to H (given by projection onto each coordinate of the vertices) and any other graph that has a homomorphism to both G and H has a homomorphism to G × H.

If a graph can be represented as a tensor product, then there may be multiple different representations (tensor products do not satisfy unique factorization) but each representation has the same number of irreducible factors. Imrich (1998) gives a polynomial time algorithm for recognizing tensor product graphs and finding a factorization of any such graph.

If either G or H is bipartite, then so is their tensor product. G × H is connected if and only if both factors are connected and at least one factor is nonbipartite (Imrich and Klavžar, Theorem 5.29). The tensor product K₂ × G is sometimes called the double cover of G; if G is already bipartite, its double cover is the disjoint union of two copies of G.

The Hedetniemi conjecture gives a formula for the chromatic number of a tensor product.

[edit] References

Imrich, W. (1998). "Factoring cardinal product graphs in polynomial time". Discrete Mathematics 192: 119–144. DOI:10.1016/S0012-365X(98)00069-7. MR 1656730.