Graph product

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

• The vertex set of H is the Cartesian product V(G₁) × V(G₂), where V(G₁) and V(G₂) are the vertex sets of G₁ and G₂, respectively.
• Two vertices (u₁, u₂) and (v₁, v₂) of H are connected by an edge if and only if the vertices u₁, u₂, v₁, v₂ satisfy a condition that takes into account the edges of G₁ and G₂. The graph products differ in exactly which this condition is.

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 $\sim ̸$ denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.

Name	Condition for $(u_1,u_2)\sim (v_1,v_2)$	Number of edges $\begin{array}{cc}{n}_1=|\mathrm{V}(G_1)|& n_2=|\mathrm{V}(G_2)|\\ m_1=|\mathrm{E}(G_1)|& m_2=|\mathrm{E}(G_2)|\end{array}$	Example
Cartesian product $G1◻G2$	( $u_1$ = $v_1$ and $u_2$ $\sim$ $v_2$ ) or ( $u_1$ $\sim$ $v_1$ and $u_2$ = $v_2$ )	$m_2{n}_1+m_1{n}_2$
Tensor product (Kronecker product, categorical product) $G_1\times G_2$	$u_1$ $\sim$ $v_1$ and  $u_2$ $\sim$ $v_2$	$2m_1{m}_2$
Lexicographical product $G_1\cdot G_2$ or $G_1[G_2]$	u1 ∼ v1 or ( u1 = v1 and u2 ∼ v2 )	$m_2{n}_1+m_1{n}_2^2$	Error creating thumbnail: Unable to save thumbnail to destination
Strong product (Normal product, AND product) $G_1⊠G_2$	( u1 = v1 and u2 ∼ v2 ) or ( u1 ∼ v1 and u2 = v2 ) or ( u1 ∼ v1 and u2 ∼ v2 )	$n_1{m}_2+n_2{m}_1+2m_1{m}_2$
Co-normal product (disjunctive product, OR product) $G_1*G_2$	u1 ∼ v1 or u2 ∼ v2
Modular product	$(u_1\sim v_1\text{ and }{u}_2\sim v_2)$ or $(u_1\sim ̸v_1\text{ and }{u}_2\sim ̸v_2)$
Rooted product	see article	$m_2{n}_1+m_1$	File:Graph-rooted-product.svg
Zig-zag product	see article	see article	see article
Replacement product
Homomorphic product $G_1⋉G_2$	$(u_1=v_1)$ or $(u_1\sim v_1\text{ and }{u}_2\sim ̸v_2)$

In general, a graph product is determined by any condition for (u₁, u₂) ∼ (v₁, v₂) that can be expressed in terms of the statements u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁, and u₂ = v₂.

Mnemonic

Let $K_2$ be the complete graph on two vertices (i.e. a single edge). The product graphs $K_2◻K_2$, $K_2\times K_2$, and $K_2⊠K_2$ look exactly like the graph representing the operator. For example, $K_2◻K_2$ is a four cycle (a square) and $K_2⊠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.

See also

• Graph operations

References

• Imrich, Wilfried; Klavžar, Sandi (2000). Product Graphs: Structure and Recognition. Wiley. ISBN 978-0-471-37039-0{{inconsistent citations}} .