# 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 thecartesian 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 alsoassociative , 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: K

_{2}◻ K_{2}= C_{4}.

* The cartesian product of two paths is agrid graph .

* The cartesian product of twohypercube graph s is another hypercube: Q_{i}◻ Q_{j}= Q_{i+j}. More generally the cartesian product of twomedian graph s is another median graph.

* The graph of vertices and edges of an n-prism is the cartesian product graph K_{2}◻ C_{n}.

* TheRook'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::(K

_{1}+ K_{2}+ K_{2}^{2}) ◻ (K_{1}+ K_{2}^{3}) = (K_{1}+ K_{2}^{2}+ K_{2}^{4}) ◻ (K_{1}+ K_{2}),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). TheHedetniemi conjecture states a related equality for thetensor 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.TheVizing conjecture states that thedomination 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