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 following table shows the most common graph products, with \sim; 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 (u_1, u_2)  (v_1, v_2). Dimensions Example
Cartesian product
G \square H
( u_1 = v_1 and u_2 \sim v_2 )
or

( u_1 \sim v_1 and u_2 = v_2 )

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
u_1 \sim v_1 and  u_2 \sim v_2 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)}
Zig-zag product see article see article see article
Replacement product
Homomorphic product[1][2]
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 (u1, u2)  (v1, v2) 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.

See also

Notes

  1. 1 2 Roberson, David E.; Mancinska, Laura (2012). "Graph Homomorphisms for Quantum Players". arXiv:1212.1724 [quant-ph].
  2. The hom-product of [3] is the graph complement of the homomorphic product of.[1]
  3. Bačík, R.; Mahajan, S. (1995). "Semidefinite programming and its applications to NP problems". Computing and Combinatorics. Lecture Notes in Computer Science 959. p. 566. doi:10.1007/BFb0030878. ISBN 3-540-60216-X.

References

  • Imrich, Wilfried; Klavžar, Sandi (2000). Product Graphs: Structure and Recognition. Wiley. ISBN 0-471-37039-8{{inconsistent citations}} .
This article is issued from Wikipedia - version of the Wednesday, February 24, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.