Tags: #definition

product of graphs

Let $G=(V_1,E_1),H=(V_2,E_2)$ be two graphs. The product of graphs is the graph $G\times H=(V,E)$ where

• $V=V_1\times V_2$ cartesian product as sets of vertices
• There is an edge between $(u,v)$ and $(u^{\prime },v^{\prime })$ if either $u=u^{\prime }$ and $(v,v^{\prime })\in E_2$ or $v=v^{\prime }$ and $(u,u^{\prime })\in E_1$

This product is associative.

Examples