Graph product

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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)} Graph-Cartesian-product.svg
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)} Graph-tensor-product.svg
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)} Graph-lexicographic-product.svg
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)} Graph-rooted-product.svg
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[edit]

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.

See also[edit]

Notes[edit]

  1. ^ a b Roberson, David E.; Mancinska, Laura (2012). "Graph Homomorphisms for Quantum Players". arXiv:1212.1724 [quant-ph].
  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
  3. ^ The hom-product of [2] is the graph complement of the homomorphic product of.[1]

References[edit]

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