Graph product

Template:Short description

In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs $G 1$ Script error: No such module "Check for unknown parameters". and $G 2$ Script error: No such module "Check for unknown parameters". and produces a graph Template:Mvar with the following properties:

The vertex set of Template:Mvar is the Cartesian product $V (G 1) \times V (G 2)$ Script error: No such module "Check for unknown parameters"., where $V (G 1)$ Script error: No such module "Check for unknown parameters". and $V (G 2)$ Script error: No such module "Check for unknown parameters". are the vertex sets of $G 1$ Script error: No such module "Check for unknown parameters". and $G 2$ Script error: No such module "Check for unknown parameters"., respectively.
Two vertices $(a 1, a 2)$ Script error: No such module "Check for unknown parameters". and $(b 1, b 2)$ Script error: No such module "Check for unknown parameters". of Template:Mvar are connected by an edge, iff a condition about $a 1, b 1$ Script error: No such module "Check for unknown parameters". in $G 1$ Script error: No such module "Check for unknown parameters". and $a 2, b 2$ Script error: No such module "Check for unknown parameters". in $G 2$ Script error: No such module "Check for unknown parameters". is fulfilled.

The graph products differ in what exactly this condition is. It is always about whether or not the vertices $a n, b n$ Script error: No such module "Check for unknown parameters". in Template:Mvar are equal or connected by an edge.

The terminology and notation for specific graph products in the literature varies quite a lot; even if the following may be considered somewhat standard, readers are advised to check what definition a particular author uses for a graph product, especially in older texts.

Even for more standard definitions, it is not always consistent in the literature how to handle self-loops. The formulas below for the number of edges in a product also may fail when including self-loops. For example, the tensor product of a single vertex self-loop with itself is another single vertex self-loop with $E = 1$ , and not $E = 2$ as the formula $E_{G \times H} = 2 E_{G} E_{H}$ would suggest.

Overview table

The following table shows the most common graph products, with $\sim$ denoting "is connected by an edge to", and $\sim̸$ denoting non-adjacency. While $\sim̸$ does allow equality, $≄$ means they must be distinct and non-adjacent. The operator symbols listed here are by no means standard, especially in older papers.

Name	Condition for $(a_{1}, a_{2}) \sim (b_{1}, b_{2})$		Number of edges $\begin{array}{cc} v_{1} = \| V (G_{1}) \| & v_{2} = \| V (G_{2}) \| \\ e_{1} = \| E (G_{1}) \| & e_{2} = \| E (G_{2}) \| \end{array}$	Example
Name		with $a_{n} rel b_{n}$ abbreviated as ${rel}_{n}$		Example
Cartesian product (box product) $G_{1} ◻ G_{2}$	$a_{1} = b_{1} \land a_{2} \sim b_{2}$ $\lor$ $a_{1} \sim b_{1} \land a_{2} = b_{2}$	$=_{1} \sim_{2}$ $\lor$ $\sim_{1} =_{2}$	$v_{1} e_{2} + e_{1} v_{2}$	File:Graph-Cartesian-product.svg
Tensor product (Kronecker product, categorical product) $G_{1} \times G_{2}$	$a_{1} \sim b_{1} \land a_{2} \sim b_{2}$	$\sim_{1} \sim_{2}$	$2 e_{1} e_{2}$	File:Graph-tensor-product.svg
Lexicographical product $G_{1} \cdot G_{2}$ or $G_{1} [G_{2}]$	$a_{1} \sim b_{1}$ $\lor$ $a_{1} = b_{1} \land a_{2} \sim b_{2}$	$\sim_{1}$ $\lor$ $=_{1} \sim_{2}$	$v_{1} e_{2} + e_{1} v_{2}^{2}$	File:Graph-lexicographic-product.svg
Strong product (Normal product, AND product) $G_{1} ⊠ G_{2}$	$a_{1} = b_{1} \land a_{2} \sim b_{2}$ $\lor$ $a_{1} \sim b_{1} \land a_{2} = b_{2}$ $\lor$ $a_{1} \sim b_{1} \land a_{2} \sim b_{2}$	$=_{1} \sim_{2}$ $\lor$ $\sim_{1} =_{2}$ $\lor$ $\sim_{1} \sim_{2}$	$v_{1} e_{2} + e_{1} v_{2} + 2 e_{1} e_{2}$
Co-normal product (disjunctive product, OR product) $G_{1} * G_{2}$	$a_{1} \sim b_{1}$ $\lor$ $a_{2} \sim b_{2}$	$\sim_{1}$ $\lor$ $\sim_{2}$	$v_{1}^{2} e_{2} + e_{1} v_{2}^{2} - 2 e_{1} e_{2}$
Modular product	$a_{1} \sim b_{1} \land a_{2} \sim b_{2}$ $\lor$ $a_{1} ≄ b_{1} \land a_{2} ≄ b_{2}$	$\sim_{1} \sim_{2}$ $\lor$ $≃_{1} ≃_{2}$
Rooted product	see article		$v_{1} e_{2} + e_{1}$	File:Graph-rooted-product.svg
Zig-zag product	see article		see article	see article
Replacement product
Corona product
Homomorphic product^[1]Template:Refn $G_{1} ⋉ G_{2}$	$a_{1} = b_{1}$ $\lor$ $a_{1} \sim b_{1} \land a_{2} \sim̸ b_{2}$	$=_{1}$ $\lor$ $\sim_{1} \sim_{2}$	$v_{1} v_{2} (v_{2} - 1) / 2 + e_{1} (v_{2}^{2} - 2 e_{2})$

In general, a graph product is determined by any condition for $(a_{1}, a_{2}) \sim (b_{1}, b_{2})$ that can be expressed in terms of $a_{n} = b_{n}$ and $a_{n} \sim b_{n}$ .

Mnemonic

Let $K_{2}$ be the complete graph on two vertices (i.e. a single edge). The product graphs $K_{2} ◻ K_{2}$ , $K_{2} \times K_{2}$ , and $K_{2} ⊠ K_{2}$ look exactly like the graph representing the operator. For example, $K_{2} ◻ K_{2}$ is a four cycle (a square) and $K_{2} ⊠ K_{2}$ is the complete graph on four vertices.

The $G_{1} [G_{2}]$ notation for lexicographic product serves as a reminder that this product is not commutative. The resulting graph looks like substituting a copy of $G_{2}$ for every vertex of $G_{1}$ .

Notes

↑ Script error: No such module "Citation/CS1".

Script error: No such module "Check for unknown parameters".

References

Script error: No such module "citation/CS1".

[rm12-1] Script error: No such module "Citation/CS1".

[1]

Graph product

Contents

Overview table

Mnemonic

See also

Notes

References

Navigation menu

Graph product

Overview table

Mnemonic

See also

Notes

References

Navigation menu

Search