# 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$) × 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.

## Overview table

The following table shows the most common graph products, with $\sim$ denoting "is connected by an edge to", and $\not \sim$ denoting non-adjacency. While $\not \sim$ does allow equality, $\not \simeq$ means they must be distinct and non-adjacent. The operator symbols listed here are by no means standard, especially in older papers.
| Name | Condition for $(a_{1},a_{2})\sim (b_{1},b_{2})$ | Condition for $(a_{1},a_{2})\sim (b_{1},b_{2})$ | Number of edges ${\begin{array}{cc}v_{1}=\vert \mathrm {V} (G_{1})\vert &v_{2}=\vert \mathrm {V} (G_{2})\vert \\e_{1}=\vert \mathrm {E} (G_{1})\vert &e_{2}=\vert \mathrm {E} (G_{2})\vert \end{array}}$ | Example |
| Name | | with $a_{n}~{\text{rel}}~b_{n}$ abbreviated as ${\text{rel}}_{n}$ | Number of edges ${\begin{array}{cc}v_{1}=\vert \mathrm {V} (G_{1})\vert &v_{2}=\vert \mathrm {V} (G_{2})\vert \\e_{1}=\vert \mathrm {E} (G_{1})\vert &e_{2}=\vert \mathrm {E} (G_{2})\vert \end{array}}$ | Example |
| Cartesian product (box product) $G_{1}\square G_{2}$ | $a_{1}=b_{1}~\land ~a_{2}\sim b_{2}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}=b_{2}$ | $=_{1}~\sim _{2}$ $\lor$ $\sim _{1}~=_{2}$ | $v_{1}~e_{2}~+~e_{1}~v_{2}$ | |
| Tensor product (Kronecker product, categorical product) $G_{1}\times G_{2}$ | $a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}$ | $\sim _{1}~\sim _{2}$ | $2~e_{1}~e_{2}$ | |
| Lexicographical product $G_{1}\cdot G_{2}$ or $G_{1}[G_{2}]$ | $a_{1}\sim b_{1}$ $\lor$ $a_{1}=b_{1}~\land ~a_{2}\sim b_{2}$ | $\sim _{1}$ $\lor$ $=_{1}~\sim _{2}$ | $v_{1}~e_{2}~+~e_{1}~v_{2}^{2}$ | |
| Strong product (Normal product, AND product) $G_{1}\boxtimes G_{2}$ | $a_{1}=b_{1}~\land ~a_{2}\sim b_{2}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}=b_{2}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}$ | $=_{1}~\sim _{2}$ $\lor$ $\sim _{1}~=_{2}$ $\lor$ $\sim _{1}~\sim _{2}$ | $v_{1}~e_{2}~+~e_{1}~v_{2}~+~2~e_{1}~e_{2}$ | |
| Co-normal product (disjunctive product, OR product) $G_{1}*G_{2}$ | $a_{1}\sim b_{1}$ $\lor$ $a_{2}\sim b_{2}$ | $\sim _{1}$ $\lor$ $\sim _{2}$ | $v_{1}^{2}~e_{2}~+~e_{1}~v_{2}^{2}~-~2~e_{1}~e_{2}$ | |
| Modular product | $a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}$ $\lor$ $a_{1}\not \simeq b_{1}~\land ~a_{2}\not \simeq b_{2}$ | $\sim _{1}~\sim _{2}$ $\lor$ $\not \simeq _{1}~\not \simeq _{2}$ | | |
| Rooted product | see article | | $v_{1}~e_{2}~+~e_{1}$ | |
| Zig-zag product | see article | | see article | see article |
| Replacement product | | | | |
| Homomorphic product $G_{1}\ltimes G_{2}$ | $a_{1}=b_{1}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}\not \sim b_{2}$ | $=_{1}$ $\lor$ $\sim _{1}~\not \sim _{2}$ | $v_{1}v_{2}(v_{2}-1)/2+e_{1}(v_{2}^{2}-2e_{2})$ | |
In general, a graph product is determined by any condition for $(a_{1},a_{2})\sim (b_{1},b_{2})$ that can be expressed in terms of $a_{n}=b_{n}$ and $a_{n}\sim b_{n}$.

## Mnemonic

Let $K_{2}$ be the complete graph on two vertices (i.e. a single edge). The product graphs $K_{2}\square K_{2}$, $K_{2}\times K_{2}$, and $K_{2}\boxtimes K_{2}$ look exactly like the graph representing the operator. For example, $K_{2}\square K_{2}$ is a four cycle (a square) and $K_{2}\boxtimes K_{2}$ is the complete graph on four vertices.
The $G_{1}[G_{2}]$ notation for lexicographic product serves as a reminder that this product is not commutative. The resulting graph looks like substituting a copy of $G_{2}$ for every vertex of $G_{1}$.