Graph product

In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs $G 1$ and $G 2$ and produces a graph $H$ with the following properties:

The vertex set of $H$ is the Cartesian product $V (G 1) \times V (G 2)$ , where $V (G 1)$ and $V (G 2)$ are the vertex sets of $G 1$ and $G 2$ , respectively.
Two vertices $(a 1, a 2)$ and $(b 1, b 2)$ of $H$ are connected by an edge, iff a condition about $a 1, b 1$ in $G 1$ and $a 2, b 2$ in $G 2$ is fulfilled.

The graph products differ in what exactly this condition is. It is always about whether or not the vertices $a n, b n$ in $G n$ are equal or connected by an edge.

The terminology and notation for specific graph products in the literature varies quite a lot; even if the following may be considered somewhat standard, readers are advised to check what definition a particular author uses for a graph product, especially in older texts.

Even for more standard definitions, it is not always consistent in the literature how to handle self-loops. The formulas below for the number of edges in a product also may fail when including self-loops. For example, the tensor product of a single vertex self-loop with itself is another single vertex self-loop with $E=1$ , and not $E=2$ as the formula $E_{G\times H}=2E_{G}E_{H}$ would suggest.