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 conditions of a certain type (see below).

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 ($u_1$, $u_2$) ∼ ($v_1$, $v_2$).	Dimensions	Example
Cartesian product $G \square H$	( $u_1$ = $v_1$ and $u_2$ $\sim$ $v_2$ ) or ( $u_1$ $\sim$ $v_1$ and $u_2$ = $v_2$ )	$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) $G \times H$	$u_1$ $\sim$ $v_1$ and  $u_2$ $\sim$ $v_2$	$G_{V_1, E_1} \times H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (2 E_1 E_2)}$
Lexicographical product $G \cdot H$ or $G[H]$	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) $G \boxtimes H$	( 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) $G * H$	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)}$
Zig-zag product	see article	see article	see article
Replacement product
Homomorphic product[1][2] $G \ltimes H$	$(u_1 = v_1)$ or $(u_1 \sim v_1 \text{ and } u_2 \not\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 \square K_2$, $K_2 \times K_2$, and $K_2 \boxtimes K_2$ look exactly like the glyph 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[H]$ notation for lexicographic product serves as a reminder that this product is not commutative.

See also

• Graph operations

Notes

1. Roberson, David E.; Mancinska, Laura (2012). "Graph Homomorphisms for Quantum Players". arXiv:1212.1724 [quant-ph].
2. The hom-product of ^[3] is the graph complement of the homomorphic product of.^[1]
3. Bačík, R.; Mahajan, S. (1995). "Semidefinite programming and its applications to NP problems". Computing and Combinatorics. Lecture Notes in Computer Science 959. p. 566. doi:10.1007/BFb0030878. ISBN 3-540-60216-X.

References

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