Graph product
Binary operation on graphs
title: "Graph product" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["graph-products"] description: "Binary operation on graphs" topic_path: "general/graph-products" source: "https://en.wikipedia.org/wiki/Graph_product" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0
::summary Binary operation on graphs ::
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, b in G 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} = 2 E_{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 \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.
::data[format=table]
| 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 | with a_n \text{rel} b_n
abbreviated as \text{rel}_n |
|---|---|---|---|---|
| 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 | [[Image:Graph-Cartesian-product.svg|200px]] |
| 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 | [[Image:Graph-tensor-product.svg|200px]] |
| 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 | [[Image:Graph-lexicographic-product.svg|200px]] |
| 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 productG_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 | [[Image:Graph-rooted-product.svg|200px]] |
| Zig-zag product | see article | | see article | see article |
| Replacement product | | | | |
| arxiv=1212.1724|last1= Roberson|first1= David E.|title= Graph Homomorphisms for Quantum Players|last2= Mancinska|first2= Laura|year= 2012|doi=10.1016/j.jctb.2015.12.009|volume=118|journal=Journal of Combinatorial Theory, Series B|pages=228–267}}
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 - 2 e_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 \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.
Notes
References
- {{Cite book| last1 = Imrich | first1 = Wilfried | last2 = Klavžar | first2 = Sandi | title = Product Graphs: Structure and Recognition | publisher = Wiley | year = 2000 | isbn = 978-0-471-37039-0}}
References
- [https://arxiv.org/pdf/1212.4129 Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More], Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, 2012
- (2012). "Graph Homomorphisms for Quantum Players". Journal of Combinatorial Theory, Series B.
- (1995). "Computing and Combinatorics".
::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::