Tensor product of graphs

In graph theory, the tensor product $G \times H$ of graphs $G$ and $H$ is a graph such that

the vertex set of $G \times H$ is the Cartesian product $V (G) \times 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.^[1]

The notation $G \times H$ 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.^[2] This product should not be confused with the strong product of graphs.

Examples

The tensor product $G \times K 2$ is a bipartite graph, called the bipartite double cover of $G$ . The bipartite double cover of the Petersen graph is the Desargues graph: $K 2 \times G (5,2) = G (10,3)$ . The bipartite double cover of a complete graph $K n$ is a crown graph (a complete bipartite graph $K n, 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 \times H$ corresponds to a pair of homomorphisms to $G$ and to $H$ . In particular, a graph $I$ admits a homomorphism into $G \times 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 $f G : I \to G$ and $f H : I \to H$ yields a homomorphism

{\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 \to G \times H$ can be composed with the projections homomorphisms

{\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}}

to yield homomorphisms to $G$ and to $H$ .

The adjacency matrix of $G \times H$ is the Kronecker (tensor) product of the adjacency matrices of $G$ and $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 \times H$ is connected if and only if both factors are connected and at least one factor is nonbipartite.^[3] In particular the bipartite double cover of $G$ is connected if and only if $G$ is connected and nonbipartite.

The Hedetniemi conjecture, which gave a formula for the chromatic number of a tensor product, was disproved by Yaroslav Shitov (2019).

The tensor product of graphs equips the category of graphs and graph homomorphisms with the structure of a symmetric closed monoidal category. Let $G 0$ denote the underlying set of vertices of the graph $G$ . The internal hom $[G, H]$ has functions $f : G 0 \to H 0$ as vertices and an edge from $f : G 0 \to H 0$ to $f' : G 0 \to H 0$ whenever an edge ${x, y}$ in $G$ implies ${f (x), f ' (y)}$ in $H$ .^[4]

Notes

^ Weichsel 1962.
^ Hahn & Sabidussi 1997.
^ Imrich & Klavžar 2000, Theorem 5.29
^ Brown et al. 2008; see also this proof

References

Brown, R.; Morris, I.; Shrimpton, J.; Wensley, C. D. (2008), "Graphs of Morphisms of Graphs", The Electronic Journal of Combinatorics, 15: A1.
Hahn, Geňa; Sabidussi, Gert (1997), Graph symmetry: algebraic methods and applications, NATO Advanced Science Institutes Series, vol. 497, Springer, p. 116, ISBN 978-0-7923-4668-5.
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
Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8
Shitov, Yaroslav (May 2019), Counterexamples to Hedetniemi's conjecture, arXiv:1905.02167
Weichsel, Paul M. (1962), "The Kronecker product of graphs", Proceedings of the American Mathematical Society, 13 (1): 47–52, doi:10.2307/2033769, JSTOR 2033769, MR 0133816
Whitehead, A. N.; Russell, B. (1912), Principia Mathematica, Cambridge University Press, vol. 2, p. 384

External links

Nicolas Bray. "Graph Tensor Product". MathWorld.

[FOOTNOTEWeichsel1962-1] Weichsel 1962.

[FOOTNOTEHahnSabidussi1997-2] Hahn & Sabidussi 1997.

[3] Imrich & Klavžar 2000, Theorem 5.29

[FOOTNOTEBrownMorrisShrimptonWensley2008-4] Brown et al. 2008; see also this proof

[1]

[2]

[3]

[4]