Tensor product of graphs

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, relational product, Kronecker 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 (Weichsel 1962).

The notation "G" × "H" is also sometimes used to refer to the Cartesian product of graphs, 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 double cover of the Petersen graph is the Desargues graph: "K"2 × "G"(5,2) = "G"(10,3).
* The tensor product of a complete graph "Kn" 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, 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 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" × "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"2 × "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.

References

*cite journal
author = Imrich, W.
title = Factoring cardinal product graphs in polynomial time
journal = Discrete Mathematics
volume = 192
year = 1998
pages = 119–144
id = MathSciNet | id = 1656730
doi = 10.1016/S0012-365X(98)00069-7

*cite book
author = Imrich, Wilfried; Klavžar, Sandi
title = Product Graphs: Structure and Recognition
publisher = Wiley
year = 2000
id = ISBN 0-471-37039-8

*cite journal
author = Weichsel, Paul M.
title = The Kronecker product of graphs
journal = Proceedings of the American Mathematical Society
volume = 13
issue = 1
year = 1962
pages = 47–52
id = MathSciNet | id = 0133816
doi = 10.2307/2033769

*cite book
author = Whitehead, A. N.; Russell, B.
title = Principia Mathematica
publisher = Cambridge University Press
year = 1912
pages = vol. 2, p. 384

External links

*mathworld | title = Graph Categorical Product | urlname = GraphCategoricalProduct


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Tensor product — In mathematics, the tensor product, denoted by otimes, may be applied in different contexts to vectors, matrices, tensors, vector spaces, algebras, topological vector spaces, and modules. In each case the significance of the symbol is the same:… …   Wikipedia

  • Cartesian product of graphs — In graph theory, the cartesian 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 either ** u = v and …   Wikipedia

  • Graph product — A graph product is a binary operation on graphs. There are several similarly defined operations on graphs, called product . Given two graphs G1 and G2 , their product H is a graph such that * the vertex set of H is the Cartesian product V(G 1)… …   Wikipedia

  • Cartesian product — Cartesian square redirects here. For Cartesian squares in category theory, see Cartesian square (category theory). In mathematics, a Cartesian product (or product set) is a construction to build a new set out of a number of given sets. Each… …   Wikipedia

  • Direct product — In mathematics, one can often define a direct product of objects already known, giving a new one. This is generally the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one… …   Wikipedia

  • Kronecker product — In mathematics, the Kronecker product, denoted by otimes, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a special case of a tensor product. The Kronecker product should not be confused with the usual matrix… …   Wikipedia

  • Hedetniemi's conjecture — In graph theory, Hedetniemi s conjecture concerns the connection between graph coloring and the tensor product of graphs. This conjecture states that:χ( G × H ) = min {χ( G ), χ( H )}.Here χ( G ) denotes the chromatic number of an undirected… …   Wikipedia

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • List of mathematics articles (T) — NOTOC T T duality T group T group (mathematics) T integration T norm T norm fuzzy logics T schema T square (fractal) T symmetry T table T theory T.C. Mits T1 space Table of bases Table of Clebsch Gordan coefficients Table of divisors Table of Lie …   Wikipedia

  • Vizing's conjecture — In graph theory, Vizing s conjecture concerns a relation between the domination number and the cartesian product of graphs. This conjecture was first stated by V. G. Vizing (1968), and states that, if γ( G ) denotes the minimum number of vertices …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”