Graph product

In mathematics, a graph product is a certain kind of 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 (u₁, u₂) and (v₁, v₂) of H are connected by an edge if and only if the vertices u₁, u₂, v₁, v₂ 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”:

Name	Condition for (u1, u2) ∼ (v1, v2).	Dimensions	Example
Cartesian product	( u1 = v1 and u2 ∼ v2 ) or ( u1 ∼ v1 and u2 = v2 )	$G_{V_1, E_1} \square H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1 V_2)}$
Tensor product	u1 ∼ v1  and  u2 ∼ v2	$G_{V_1, E_1} \times H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (2 E_1 E_2)}$
Lexicographical product	u1 ∼ v1 or ( u1 = v1 and u2 ∼ v2 )	$G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1 V_2^2)}$
Strong product (Normal product, AND product)	( u1 = v1 and u2 ∼ v2 ) or ( u1 ∼ v1 and u2 = v2 ) or ( u1 ∼ v1 and u2 ∼ v2 )	$G_{V_1, E_1} \boxtimes H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (V_1 E_2 + V_2E_1 + 2 E_1 E_2)}$
Co-normal product (disjunctive product, OR product)	u1 ∼ v1 or u2 ∼ v2
Rooted product	see article	$G_{V_1, E_1} \cdot H_{V_2, E_2} \rightarrow J_{(V_1 V_2), (E_2 V_1 + E_1)}$

In general, a graph product is determined by any condition for (u₁, u₂) ∼ (v₁, v₂) that can be expressed in terms of the statements u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁, and u₂ = v₂.

See also

• Graph operations

References

• Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8 .