Cartesian Product of Graphs

• The Cartesian Product of graphs and is defined as

  such that and vertices and in are adjacent if and only if either the following hold (1) and is an edge in (2) and is an edge in .

  • The Cartesian Product is both commutative and associative.
  • The Cartesian Product preserves connectedness.

• A graph is prime if the identity suggests that either or are trivial.

• (Mesbahi 3.24) Every connected graph can be written as a Cartesian Product of prime graphs. Such a decomposition is unique up to reordering of factors ¹

Links §

• Mesbahi and Egerstedt

Footnotes §

1. This is analogous to the Fundamental Theorem of Finitely Generated Abelian Groups ↩