In graph theory

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, 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
  If and only if
  In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
  
   u' is adjacent with v' and u is adjacent with v.

The tensor product is also called the direct product, categorical product, cardinal product, relational product, Kronecker product, weak direct product, or conjunction. As an operation on binary relations, the tensor product was introduced by Alfred North Whitehead

Alfred North Whitehead

Alfred North Whitehead, OM FRS was an English mathematician who became a philosopher. He wrote on algebra, logic, foundations of mathematics, philosophy of science, physics, metaphysics, and education...

 and Bertrand Russell

Bertrand Russell

Bertrand Arthur William Russell, 3rd Earl Russell, OM, FRS was a British philosopher, logician, mathematician, historian, and social critic. At various points in his life he considered himself a liberal, a socialist, and a pacifist, but he also admitted that he had never been any of these things...

 in their Principia Mathematica

Principia Mathematica

The Principia Mathematica is a three-volume work on the foundations of mathematics, written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913...

 (1912). It is also equivalent to the Kronecker product

Kronecker product

In mathematics, the Kronecker product, denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It gives the matrix of the tensor product with respect to a standard choice of basis. The Kronecker product should not be confused with the usual matrix...

 of the adjacency matrices

Adjacency matrix

In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices...

 of the graphs (Weichsel 1962).

The notation G × H is also sometimes used to represent another construction known as the Cartesian product of graphs

Cartesian product of graphs

In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...

, but more commonly refers to the tensor product. The cross symbol shows visually the two edges resulting from the tensor product of two edges.

Examples

• The tensor product G × K₂ is a bipartite graph
  Bipartite graph
  In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
  
  , called the bipartite double cover
  Bipartite double cover
  In graph theoretic mathematics, the bipartite double cover of an undirected graph G is a bipartite covering graph of G, with twice as many vertices as G. It can be constructed as the tensor product of graphs G × K2...
  
   of G. The bipartite double cover of the Petersen graph
  Petersen graph
  In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
  
   is the Desargues graph
  Desargues graph
  In the mathematical field of graph theory, the Desargues graph is a distance-transitive cubic graph with 20 vertices and 30 edges. It is named after Gérard Desargues, arises from several different combinatorial constructions, has a high level of symmetry, is the only known non-planar cubic partial...
  
  : K₂ × G(5,2) = G(10,3). The bipartite double cover of a complete graph
  Complete graph
  In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.-Properties:...
  
   K_n is a crown graph
  Crown graph
  In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j...
  
   (a complete bipartite graph
  Complete bipartite graph
  In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.- Definition :...
  
   K_n,n minus a perfect matching).
• The tensor product of a complete graph with itself is the complement of a Rook's graph
  Rook's graph
  In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move...
  
  . 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

Product (category theory)

In category theory, the product of two objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the cartesian product of sets, the direct product of groups, the direct product of rings and the product of topological spaces...

 in the category of graphs and graph homomorphism

Graph homomorphism

In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices.-Definitions:...

s. That is, there is a homomorphism from G × H to G and to H (given by projection onto each coordinate of the vertices) such that any other graph that has a homomorphism to both G and H has a homomorphism to G × H that factors through the homomorphisms to G and H.

The adjacency matrix of G × H is the tensor product

Kronecker product

In mathematics, the Kronecker product, denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It gives the matrix of the tensor product with respect to a standard choice of basis. The Kronecker product should not be confused with the usual matrix...

 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

Bipartite

Bipartite means having two parts, or an agreement between two parties. More specifically, it may refer to any of the following:-Mathematics:* 2 * bipartite graph* bipartite cubic, a type of cubic function-Medicine:...

, 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). In particular the bipartite double cover of G is connected if and only if G is connected and nonbipartite.

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