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(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 conditions of a certain type (see below).
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.
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
K
2
be the complete graph on two vertices (i.e. a single edge). The product graphs
K
2
◻
K
2
,
K
2
×
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
[
H
]
notation for lexicographic product serves as a reminder that this product is not commutative.
