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(G1) × V(G2), where V(G1) and V(G2) are the vertex sets of G1 and G2, respectively.
• Two vertices (u1u2) and (v1v2) 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 $\not\sim$ denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.

Name Condition for (u1u2) ∼ (v1v2). Dimensions Example
Cartesian product
$G \square H$
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
(Categorical product)
$G \times H$
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
$G \cdot H$ or $G[H]$
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)
$G \boxtimes H$
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)
$G * H$
u1 ∼ v1
or
u2 ∼ v2
Modular product $(u_1 \sim v_1 \text{ and } u_2 \sim v_2)$
or

$(u_1 \not\sim v_1 \text{ and } u_2 \not\sim v_2)$

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)}$
Kronecker product see article see article see article
Zig-zag product see article see article see article
Replacement product
Homomorphic product[1][3]
$G \ltimes H$
$(u_1 = v_1)$
or
$(u_1 \sim v_1 \text{ and } u_2 \not\sim v_2)$

In general, a graph product is determined by any condition for (u1u2) ∼ (v1v2) that can be expressed in terms of the statements u1 ∼ v1, u2 ∼ v2, u1 = v1, and u2 = v2.

Mnemonic

Let $K_2$ be the complete graph on two vertices (i.e. a single edge). The product graphs $K_2 \square K_2$, $K_2 \times K_2$, and $K_2 \boxtimes K_2$ look exactly like the glyph representing the operator. For example, $K_2 \square K_2$ is a four cycle (a square) and $K_2 \boxtimes 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.

2. ^ Bačík, R.; Mahajan, S. (1995). "Computing and Combinatorics". Lecture Notes in Computer Science 959. p. 566. doi:10.1007/BFb0030878. ISBN 3-540-60216-X. |chapter= ignored (help) edit