Graph product

In mathematics, a graph product is a 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 $\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]$	u₁ ∼ v₁ or ( u₁ = v₁ and u₂ ∼ v₂ )	$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$	( u₁ = v₁ and u₂ ∼ v₂ ) or ( u₁ ∼ v₁ and u₂ = v₂ ) or ( u₁ ∼ v₁ and u₂ ∼ v₂ )	$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$	u₁ ∼ v₁ or u₂ ∼ v₂
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]^[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 (u₁, u₂) ∼ (v₁, v₂) that can be expressed in terms of the statements u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁, and u₂ = v₂.

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.

Notes

1 2 Roberson, David E.; Mancinska, Laura (2012). "Graph Homomorphisms for Quantum Players". arXiv:1212.1724 [quant-ph].
↑ The hom-product of ^[3] is the graph complement of the homomorphic product of.^[1]
↑ 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 Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Graph product

Mnemonic

See also

Notes

References