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' in H, or
  • u' = v' and u is adjacent with v in G.

Cartesian product graphs can be recognized efficiently, in time O(m log n) for a graph with m edges and n vertices (Aurenhammer, Hagauer & Imrich 1992). The operation is commutative as an operation on isomorphism classes of graphs, and more strongly the graphs G H and H G are naturally isomorphic, but it is not commutative as an operation on labeled graphs. The operation is also associative, as the graphs (F G) H and F (G H) are naturally isomorphic.

The notation G × H is occasionally also used for Cartesian products of graphs, but is more commonly used for another construction known as 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. (The tensor product is the categorical product.) The category of graphs does form a monoidal category under the Cartesian product.