# 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 ∼ denoting “is connected by an edge to”, and $\not\sim$ denoting non-connection:

Name Condition for (u1u2) ∼ (v1v2). Dimensions Example
Cartesian product u1 = v1 and u2 ∼ v2 )
or

u1 ∼ v1 and u2 = v2 )

$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)
u1 ∼ v1  and  u2 ∼ v2 $G_{V_1, E_1} \times H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (2 E_1 E_2)}$
Lexicographical product u1 ∼ v1
or
u1 = v1 and u2 ∼ v2 )
$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)
u1 = v1 and u2 ∼ v2 )
or
u1 ∼ v1 and u2 = v2 )
or
u1 ∼ v1 and u2 ∼ v2 )
$G_{V_1, E_1} \boxtimes H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (V_1 E_2 + V_2E_1 + 2 E_1 E_2)}$
Co-normal product
(disjunctive product, OR product)
u1 ∼ v1
or
u2 ∼ v2
Modular product $(u_1 \sim v_1 \text{ and } u_2 \sim v_2)$
or

$(u_1 \not\sim v_1 \text{ and } u_2 \not\sim v_2)$

Rooted product see article $G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1)}$
Kronecker product see article see article see article
Zig-zag product see article see article see article

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.