Encyclopedia

Graph product

Binary operation on graphs

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated November 16, 2025

In graph theory, 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 (a₁,a₂) and (b₁,b₂) of H are connected by an edge, iff a condition about a₁, b₁ in G₁ and a₂, b₂ in G₂ is fulfilled.

The graph products differ in what exactly this condition is. It is always about whether or not the vertices a_n, b_n in G_n 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.

01Overview table

The following table shows the most common graph products, with $\sim$ denoting "is connected by an edge to", and $\not \sim$ denoting non-adjacency. While $\not \sim$ does allow equality, $\not \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}=\vert \mathrm {V} (G_{1})\vert &v_{2}=\vert \mathrm {V} (G_{2})\vert \\e_{1}=\vert \mathrm {E} (G_{1})\vert &e_{2}=\vert \mathrm {E} (G_{2})\vert \end{array}}$	Example
Name		with $a_{n}~{\text{rel}}~b_{n}$ abbreviated as ${\text{rel}}_{n}$		Example
Cartesian product (box product) $G_{1}\square G_{2}$	$a_{1}=b_{1}~\land ~a_{2}\sim b_{2}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}=b_{2}$	$=_{1}~\sim _{2}$ $\lor$ $\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}~\land ~a_{2}\sim b_{2}$	$\sim _{1}~\sim _{2}$	$2~e_{1}~e_{2}$
Strong product (Normal product, AND product) $G_{1}\boxtimes G_{2}$ $=(G_{1}\times G_{2})\cup (G_{1}\square G_{2})$	$a_{1}=b_{1}~\land ~a_{2}\sim b_{2}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}=b_{2}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}$	$=_{1}~\sim _{2}$ $\lor$ $\sim _{1}~=_{2}$ $\lor$ $\sim _{1}~\sim _{2}$	$v_{1}~e_{2}~+~e_{1}~v_{2}~+~2~e_{1}~e_{2}$
Lexicographical product $G_{1}\cdot G_{2}$ or $G_{1}[G_{2}]$	$a_{1}\sim b_{1}$ $\lor$ $a_{1}=b_{1}~\land ~a_{2}\sim b_{2}$	$\sim _{1}$ $\lor$ $=_{1}~\sim _{2}$	$v_{1}~e_{2}~+~e_{1}~v_{2}^{2}$
Co-normal product (disjunctive product, OR product) $G_{1}*G_{2}$ or $G_{1}\lor G_{2}$ $=G_{1}[G_{2}]\cup G_{2}[G_{1}]$ $={\overline {\;{\overline {G_{1}}}\boxtimes {\overline {G_{2}}}\;}}$	$a_{1}\sim b_{1}$ $\lor$ $a_{2}\sim b_{2}$	$\sim _{1}$ $\lor$ $\sim _{2}$	$v_{1}^{2}~e_{2}~+~e_{1}~v_{2}^{2}~-~2~e_{1}~e_{2}$
Modular product $G_{1}\diamond G_{2}$ $=(G_{1}\boxtimes G_{2})\cup ({\overline {G_{1}}}\times {\overline {G_{2}}})$	$a_{1}\sim b_{1}~\land ~a_{2}\sim b_{2}$ $\lor$ $a_{1}\not \simeq b_{1}~\land ~a_{2}\not \simeq b_{2}$	$\sim _{1}~\sim _{2}$ $\lor$ $\not \simeq _{1}~\not \simeq _{2}$
Rooted product	see article		$v_{1}~e_{2}~+~e_{1}$
Zig-zag product	see article		see article	see article
Replacement product
Homomorphic product $G_{1}\ltimes G_{2}$	$a_{1}=b_{1}$ $\lor$ $a_{1}\sim b_{1}~\land ~a_{2}\not \sim b_{2}$	$=_{1}$ $\lor$ $\sim _{1}~\not \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}$ .

02Mnemonic

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 graph 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_{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}$ .

Watch videos about Graph productExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Graph product”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Graph product

01Overview table

02Mnemonic

Sources and credits

Related topics

Graph operations