# 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 (u1u2) and (v1v2) of H are connected by an edge if and only if the vertices u1, u2, v1, v2 satisfy conditions of a certain type (see below).

The following table shows the most common graph products, with ${\displaystyle \sim }$; denoting “is connected by an edge to”, and ${\displaystyle \not \sim }$ denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.

Name Condition for (${\displaystyle u_{1}}$${\displaystyle u_{2}}$) ∼ (${\displaystyle v_{1}}$${\displaystyle v_{2}}$). Dimensions Example
Cartesian product
${\displaystyle G\square H}$
${\displaystyle u_{1}}$ = ${\displaystyle v_{1}}$ and ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$ )
or

${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ and ${\displaystyle u_{2}}$ = ${\displaystyle v_{2}}$ )

${\displaystyle G_{V_{1},E_{1}}\square H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1}V_{2})}}$
Tensor product
(Categorical product)
${\displaystyle G\times H}$
${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ and  ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$ ${\displaystyle G_{V_{1},E_{1}}\times H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(2E_{1}E_{2})}}$
Lexicographical product
${\displaystyle G\cdot H}$ or ${\displaystyle G[H]}$
u1 ∼ v1
or
u1 = v1 and u2 ∼ v2 )
${\displaystyle G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1}V_{2}^{2})}}$
Strong product
(Normal product, AND product)
${\displaystyle G\boxtimes H}$
u1 = v1 and u2 ∼ v2 )
or
u1 ∼ v1 and u2 = v2 )
or
u1 ∼ v1 and u2 ∼ v2 )
${\displaystyle G_{V_{1},E_{1}}\boxtimes H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(V_{1}E_{2}+V_{2}E_{1}+2E_{1}E_{2})}}$
Co-normal product
(disjunctive product, OR product)
${\displaystyle G*H}$
u1 ∼ v1
or
u2 ∼ v2
Modular product ${\displaystyle (u_{1}\sim v_{1}{\text{ and }}u_{2}\sim v_{2})}$
or

${\displaystyle (u_{1}\not \sim v_{1}{\text{ and }}u_{2}\not \sim v_{2})}$

Rooted product see article ${\displaystyle G_{V_{1},E_{1}}\cdot H_{V_{2},E_{2}}\rightarrow J_{(V_{1}V_{2}),(E_{2}V_{1}+E_{1})}}$
Zig-zag product see article see article see article
Replacement product
Homomorphic product[1][3]
${\displaystyle G\ltimes H}$
${\displaystyle (u_{1}=v_{1})}$
or
${\displaystyle (u_{1}\sim v_{1}{\text{ and }}u_{2}\not \sim v_{2})}$

In general, a graph product is determined by any condition for (u1u2) ∼ (v1v2) that can be expressed in terms of the statements u1 ∼ v1, u2 ∼ v2, u1 = v1, and u2 = v2.

## Mnemonic

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