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.
