Graph product

In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs Template:Math and Template:Math and produces a graph Template:Mvar with the following properties:

• The vertex set of Template:Mvar is the Cartesian product Template:Math, where Template:Math and Template:Math are the vertex sets of Template:Math and Template:Math, respectively.
• Two vertices Template:Math and Template:Math of Template:Mvar are connected by an edge, iff a condition about Template:Math in Template:Math and Template:Math in Template:Math is fulfilled.

The graph products differ in what exactly this condition is. It is always about whether or not the vertices Template:Math in Template:Mvar 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.

Even for more standard definitions, it is not always consistent in the literature how to handle self-loops. The formulas below for the number of edges in a product also may fail when including self-loops. For example, the tensor product of a single vertex self-loop with itself is another single vertex self-loop with $E=1$, and not $E=2$ as the formula $E_{G\times H}=2E_G{E}_H$ would suggest.

Overview table

The following table shows the most common graph products, with $\sim$ denoting "is connected by an edge to", and $\sim ̸$ denoting non-adjacency. While $\sim ̸$ does allow equality, $\simeq ̸$ means they must be distinct and non-adjacent. 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=|\mathrm{V}(G_1)|& v_2=|\mathrm{V}(G_2)|\\ e_1=|\mathrm{E}(G_1)|& e_2=|\mathrm{E}(G_2)|\end{array}$	Example
		with $a_n\text{rel}{b}_n$ abbreviated as ${\text{rel}}_n$
Cartesian product (box product) $G_1◻G_2$	$a_1=b_1\wedge a_2\sim b_2$ $\vee$ $a_1\sim b_1\wedge a_2=b_2$	${=}_1{\sim }_2$ $\vee$ ${\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\wedge a_2\sim b_2$	${\sim }_1{\sim }_2$	$2e_1{e}_2$
Lexicographical product $G_1\cdot G_2$ or $G_1[G_2]$	$a_1\sim b_1$ $\vee$ $a_1=b_1\wedge a_2\sim b_2$	${\sim }_1$ $\vee$ ${=}_1{\sim }_2$	$v_1{e}_2+e_1{v}_2^2$
Strong product (Normal product, AND product) $G_1⊠G_2$	$a_1=b_1\wedge a_2\sim b_2$ $\vee$ $a_1\sim b_1\wedge a_2=b_2$ $\vee$ $a_1\sim b_1\wedge a_2\sim b_2$	${=}_1{\sim }_2$ $\vee$ ${\sim }_1{=}_2$ $\vee$ ${\sim }_1{\sim }_2$	$v_1{e}_2+e_1{v}_2+2e_1{e}_2$
Co-normal product (disjunctive product, OR product) $G_1*G_2$	$a_1\sim b_1$ $\vee$ $a_2\sim b_2$	${\sim }_1$ $\vee$ ${\sim }_2$	$v_1^2{e}_2+e_1{v}_2^2-2e_1{e}_2$
Modular product	$a_1\sim b_1\wedge a_2\sim b_2$ $\vee$ $a_1\simeq ̸b_1\wedge a_2\simeq ̸b_2$	${\sim }_1{\sim }_2$ $\vee$ ${\simeq }_1{\simeq }_2$
Rooted product	see article		$v_1{e}_2+e_1$
Zig-zag product	see article		see article	see article
Replacement product
Homomorphic productTemplate:Refn $G_1⋉G_2$	$a_1=b_1$ $\vee$ $a_1\sim b_1\wedge a_2\sim ̸b_2$	${=}_1$ $\vee$ ${\sim }_1{\sim }_2$	$v_1{v}_2(v_2-1)/2+e_1(v_2^2-2e_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◻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. The resulting graph looks like substituting a copy of $G_2$ for every vertex of $G_1$.

See also

• Graph operations

References

• Template:Cite book