Cartesian product of graphs

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 "u' " is adjacent with "v' ", or
** "u' " = "v' " and "u" is adjacent with "v".

Cartesian product graphs can be recognized efficiently, in time O("m" log "n") for a graph with "m" edges and "n" vertices (Aurenhammer et al., 1992). The operation is essentially commutative, as the graphs "G" ◻ "H" and "H" ◻ "G" are isomorphic. The operation is also associative, as the graphs ("F" ◻ "G") ◻ "H" and "F" ◻ ("G" ◻ "H") are isomorphic.

The notation "G" × "H" is occasionally also used for Cartesian products of graphs, but more commonly refers to the tensor product of graphs. The square symbol is the more common and unambiguous notation for the Cartesian product of graphs. It shows visually the four edges resulting from the Cartesian product of two edges.

The cartesian product is "not" a product in the category of graphs, but only a tensor product (in a category theoretical sense).

Examples

* The cartesian product of two edges is a cycle on four vertices: K2 ◻ K2 = C4.
* The cartesian product of two paths is a grid graph.
* The cartesian product of two hypercube graphs is another hypercube: Qi ◻ Qj = Qi+j. More generally the cartesian product of two median graphs is another median graph.
* The graph of vertices and edges of an n-prism is the cartesian product graph K2 ◻ Cn.
* The Rook's graph is the cartesian product of two complete graphs.

Properties

If a connected graph is a cartesian product, it can be factorized uniquely as a product of prime factors, graphs that cannot themselves be decomposed as products of graphs (Sabidussi 1960; Vizing 1963). However, Imrich and Klavžar (2000) describe a disconnected graph that can be expressed in two different ways as a cartesian product of prime graphs::(K1 + K2 + K22) ◻ (K1 + K23) = (K1 + K22 + K24) ◻ (K1 + K2),where the plus sign denotes disjoint union and the superscripts denote exponentiation over cartesian products.

A cartesian product is vertex-transitive if and only if each of its factors is (Imrich and Klavžar, Theorem 4.19).

The chromatic number of the cartesian product satisfies the equation :χ(G ◻ H) = max {χ(G), χ(H)}(Sabidussi 1957). The Hedetniemi conjecture states a related equality for the tensor product of graphs. The independence number of a cartesian product is not so easily calculated, but as Vizing (1963) showed it satisfies the inequalities:α("G")α("H") + min.The Vizing conjecture states that the domination number of a cartesian product satisfies the inequality:γ("G" ◻ "H") ≥ γ("G")γ("H").

References

*cite journal
author = Aurenhammer, F.; Hagauer, J.; Imrich, W.
title = Cartesian graph factorization at logarithmic cost per edge
year = 1992
journal = Comput. Complexity
volume = 2
pages = 331–349
id = MathSciNet | id = 1215316
doi = 10.1007/BF01200428

*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 = Sabidussi, G.
title = Graphs with given group and given graph-theoretical properties
journal = Canad. J. Math.
volume = 9
year = 1957
pages = 515–525
id = MathSciNet | id = 0094810

*cite journal
author = Sabidussi, G.
title = Graph multiplication
journal = Math. Z.
volume = 72
year = 1960
pages = 446–457
id = MathSciNet | id = 0209177
doi = 10.1007/BF01162967

*cite journal
author = Vizing, V. G.
title = The Cartesian product of graphs
journal = Vycisl. Sistemy
volume = 9
year = 1963
pages = 30–43
id = MathSciNet | id = 0209178

External links

*mathworld | title = Graph Cartesian Product | urlname = GraphCartesianProduct


Wikimedia Foundation. 2010.

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

Look at other dictionaries:

  • 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

  • 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… …   Wikipedia

  • Lexicographic product of graphs — In graph theory, the lexicographic product or graph composition G ∙ H of graphs G and H is a graph such that * the vertex set of G ∙ H is the cartesian product V(G) imes V(H) ; and * any two vertices (u,u ) and (v,v ) are adjacent in G ∙ H if and …   Wikipedia

  • Modular product of graphs — The modular product of graphs. In graph theory, the modular product of graphs G and H is a graph such that the vertex set of the modular product of G and H is the cartesian product V(G) ×  V(H); and any two vertices (u, v) and (u… …   Wikipedia

  • Rooted product of graphs — In mathematical graph theory, the rooted product of a graph G and a rooted graph H is defined as follows: take | V ( G )| copies of H , and for every vertex v i of G , identify v i with the root node of the i th copy of H .More formally, assuming …   Wikipedia

  • Cartesian closed category — In category theory, a category is cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in… …   Wikipedia

  • Cartesian coordinate system — Illustration of a Cartesian coordinate plane. Four points are marked and labeled with their coordinates: (2, 3) in green, (−3, 1) in red, (−1.5, −2.5) in blue, and the origin (0, 0) in purple. A Cartesian coordinate system specifies each point… …   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

  • 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

  • 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

Share the article and excerpts

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