- The vertex set of H is the Cartesian product V(G1) × V(G2), where V(G1) and V(G2) are the vertex sets of G1 and G2, respectively.
- Two vertices (u1, u2) and (v1, v2) of H are connected by an edge if and only if the vertices u1, u2, v1, v2 satisfy a condition that takes into account the edges of G1 and G2. 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 standard, readers are advised to check what definition a particular author uses for a graph product, especially in older texts.
The following table shows the most common graph products, with denoting “is connected by an edge to”, and denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.
|Name||Condition for||Number of edges
||( = and )
( and = )
|u1 ∼ v1
( u1 = v1 and u2 ∼ v2 )
(Normal product, AND product)
|( u1 = v1 and u2 ∼ v2 )
( u1 ∼ v1 and u2 = v2 )
( u1 ∼ v1 and u2 ∼ v2 )
(disjunctive product, OR product)
|u1 ∼ v1
u2 ∼ v2
|Rooted product||see article|
|Zig-zag product||see article||see article||see article|
In general, a graph product is determined by any condition for (u1, u2) ∼ (v1, v2) that can be expressed in terms of the statements u1 ∼ v1, u2 ∼ v2, u1 = v1, and u2 = v2.
Let be the complete graph on two vertices (i.e. a single edge). The product graphs , , and look exactly like the graph representing the operator. For example, is a four cycle (a square) and is the complete graph on four vertices. The notation for lexicographic product serves as a reminder that this product is not commutative.
- Roberson, David E.; Mancinska, Laura (2012). "Graph Homomorphisms for Quantum Players". Journal of Combinatorial Theory, Series B. 118: 228–267. arXiv:1212.1724. doi:10.1016/j.jctb.2015.12.009.
- 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 978-3-540-60216-3.
- The hom-product of  is the graph complement of the homomorphic product of.