Tensor product of graphs

File:Graph-tensor-product.svg

The tensor product of graphs.

In graph theory, the tensor product Template:Math of graphs Template:Mvar and Template:Mvar is a graph such that

• the vertex set of Template:Math is the Cartesian product Template:Math; and
• vertices Template:Math and Template:Math are adjacent in Template:Math if and only if
  • Template:Mvar is adjacent to Template:Mvar in Template:Mvar, and
  • Template:Mvar is adjacent to Template:Mvar in Template:Mvar.

The tensor product is also called the direct product, Kronecker product, categorical product, cardinal product, relational product, weak direct product, or conjunction. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead and Bertrand Russell in their Principia Mathematica ([[#Template:Harvid|1912]]). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs.Template:Sfn

The notation Template:Math is also (and formerly normally was) used to represent another construction known as the Cartesian product of graphs, but nowadays more commonly refers to the tensor product. The cross symbol shows visually the two edges resulting from the tensor product of two edges.Template:Sfn This product should not be confused with the strong product of graphs.

Examples

• The tensor product Template:Math is a bipartite graph, called the bipartite double cover of Template:Mvar. The bipartite double cover of the Petersen graph is the Desargues graph: Template:Math. The bipartite double cover of a complete graph Template:Mvar is a crown graph (a complete bipartite graph Template:Math minus a perfect matching).
• The tensor product of a complete graph with itself is the complement of a Rook's graph. Its vertices can be placed in an Template:Mvar-by-Template:Mvar grid, so that each vertex is adjacent to the vertices that are not in the same row or column of the grid.

Properties

The tensor product is the category-theoretic product in the category of graphs and graph homomorphisms. That is, a homomorphism to Template:Math corresponds to a pair of homomorphisms to Template:Mvar and to Template:Mvar. In particular, a graph Template:Mvar admits a homomorphism into Template:Math if and only if it admits a homomorphism into Template:Mvar and into Template:Mvar.

To see that, in one direction, observe that a pair of homomorphisms Template:Math and Template:Math yields a homomorphism

$\{\begin{array}{l}f:I\to G\times H\\ f(v)=(f_G(v),f_H(v))\end{array}$

In the other direction, a homomorphism Template:Math can be composed with the projections homomorphisms

$\{\begin{array}{l}{\pi }_G:G\times H\to G\\ {\pi }_G((u,u^{\prime }))=u\end{array}\{\begin{array}{l}{\pi }_H:G\times H\to H\\ {\pi }_H((u,u^{\prime }))=u^{\prime }\end{array}$

to yield homomorphisms to Template:Mvar and to Template:Mvar.

The adjacency matrix of Template:Math is the Kronecker (tensor) product of the adjacency matrices of Template:Mvar and Template:Mvar.

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. Template:Harvtxt gives a polynomial time algorithm for recognizing tensor product graphs and finding a factorization of any such graph.

If either Template:Mvar or Template:Mvar is bipartite, then so is their tensor product. Template:Math is connected if and only if both factors are connected and at least one factor is nonbipartite. In particular the bipartite double cover of Template:Mvar is connected if and only if Template:Mvar is connected and nonbipartite.

The Hedetniemi conjecture, which gave a formula for the chromatic number of a tensor product, was disproved by Template:Harvs.

The tensor product of graphs equips the category of graphs and graph homomorphisms with the structure of a symmetric closed monoidal category. Let Template:Math denote the underlying set of vertices of the graph Template:Mvar. The internal hom Template:Math has functions Template:Math as vertices and an edge from Template:Math to Template:Math whenever an edge Template:Math in Template:Mvar implies Template:Math in Template:Mvar.Template:Sfn

See also

• Graph product
• Strong product of graphs

References

• .
• .