Graph product
In mathematics, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G1 and G2 and produces a graph H with the following properties:
- The vertex set of H is the Cartesian product V × V, where V and V are the vertex sets of G1 and G2, respectively.
- Two vertices and 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.
Overview table
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 | Example |
| Cartesian product | or | ||
| Tensor product | and | ||
| Lexicographical product or | u1 ∼ v1 or | ||
| Strong product | or or | ||
| Co-normal product | u1 ∼ v1 or u2 ∼ v2 | ||
| Modular product | or | ||
| Rooted product | see article | ||
| Zig-zag product | see article | see article | see article |
| Replacement product | |||
| Homomorphic product | or |
In general, a graph product is determined by any condition for ∼ that can be expressed in terms of the statements u1 ∼ v1, u2 ∼ v2, u1 = v1, and u2 = v2.