# Graph product

In mathematics, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G1 and G2 and produces a graph H with the following properties:

• The vertex set of H is the Cartesian product V(G1) × V(G2), where V(G1) and V(G2) are the vertex sets of G1 and G2, respectively.
• Two vertices (a1a2) and (b1b2) of H are connected by an edge, iff a condition about a1, b1 in G1 and a2, b2 in G2 is fulfilled.

The graph products differ in what exactly this condition is. It is always about whether or not the vertices an, bn in Gn 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.

## 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-connection. 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})$ 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
with $a_{n}~{\text{rel}}~b_{n}$ abbreviated as ${\text{rel}}_{n}$ Cartesian 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 \sim b_{1}~\land ~a_{2}\not \sim b_{2}$ $\sim _{1}~\sim _{2}$ $\lor$ $\not \sim _{1}~\not \sim _{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}$ 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.