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 vertices (g,h) and (g',h' ) are adjacent in G × H if and only if g is adjacent to g' in G, and h is adjacent to h' in H. 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 (1912). It is also equivalent to the Kronecker product of the adjacency matrices of the graphs. The notation G × H was formerly (and occasionally still is) used to represent the Cartesian product of graphs, which nowadays is usually written G □ H. The cross symbol in G × H depicts the two edges resulting from the tensor product of two edges, whereas G □ H has four resulting edges. This product should not be confused with the strong product of graphs.
Examples The tensor product G × K2 is a bipartite graph, called the bipartite double cover of G. The bipartite double cover of the Petersen graph is the Desargues graph: K2 × G(5,2) = G(10,3). The bipartite double cover of a complete graph Kn is a crown graph (a complete bipartite graph Kn,n 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 n-by-n 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 G × H corresponds to a pair of homomorphisms to G and to H. In particular, a graph I admits a homomorphism into G × H if and only if it admits a homomorphism into G and into H. To see that, in one direction, observe that a pair of homomorphisms fG : I → G and fH : I → H yields a homomorphism
{ f : I → G × H f ( v ) = ( f G ( v ) , f H ( v ) ) {\displaystyle {\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases}}}
In the other direction, a homomorphism f : I → G × H can be composed with the projections homomorphisms
{ π G : G × H → G π G ( ( u , u ′ ) ) = u { π H : G × H → H π H ( ( u , u ′ ) ) = u ′ {\displaystyle {\begin{cases}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{cases}}\qquad \qquad {\begin{cases}\pi _{H}:G\times H\to H\\\pi _{H}((u,u'))=u'\end{cases}}}
… excerpt ends here. Continue reading the full article.
