# 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 a condition that takes into account the edges of G1 and G2. The graph products differ in exactly which this condition is.

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

## Overview table

The following table shows the most common graph products, with ${\displaystyle \sim }$ denoting “is connected by an edge to”, and ${\displaystyle \not \sim }$ denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.

Name Condition for ${\displaystyle (u_{1},u_{2})\sim (v_{1},v_{2})}$ Number of edges
${\displaystyle {\begin{array}{cc}n_{1}=\vert \mathrm {V} (G_{1})\vert &n_{2}=\vert \mathrm {V} (G_{2})\vert \\m_{1}=\vert \mathrm {E} (G_{1})\vert &m_{2}=\vert \mathrm {E} (G_{2})\vert \end{array}}}$
Example
Cartesian product
${\displaystyle G_{1}\square G_{2}}$
${\displaystyle u_{1}}$ = ${\displaystyle v_{1}}$ and ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$ )
or

${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ and ${\displaystyle u_{2}}$ = ${\displaystyle v_{2}}$ )

${\displaystyle m_{2}n_{1}+m_{1}n_{2}}$
Tensor product
(Categorical product)
${\displaystyle G_{1}\times G_{2}}$
${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ and  ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$ ${\displaystyle 2m_{1}m_{2}}$
Lexicographical product
${\displaystyle G_{1}\cdot G_{2}}$ or ${\displaystyle G_{1}[G_{2}]}$
u1 ∼ v1
or
u1 = v1 and u2 ∼ v2 )
${\displaystyle m_{2}n_{1}+m_{1}n_{2}^{2}}$
Strong product
(Normal product, AND product)
${\displaystyle G_{1}\boxtimes G_{2}}$
u1 = v1 and u2 ∼ v2 )
or
u1 ∼ v1 and u2 = v2 )
or
u1 ∼ v1 and u2 ∼ v2 )
${\displaystyle n_{1}m_{2}+n_{2}m_{1}+2m_{1}m_{2}}$
Co-normal product
(disjunctive product, OR product)
${\displaystyle G_{1}*G_{2}}$
u1 ∼ v1
or
u2 ∼ v2
Modular product ${\displaystyle (u_{1}\sim v_{1}{\text{ and }}u_{2}\sim v_{2})}$
or

${\displaystyle (u_{1}\not \sim v_{1}{\text{ and }}u_{2}\not \sim v_{2})}$

Rooted product see article ${\displaystyle m_{2}n_{1}+m_{1}}$
Zig-zag product see article see article see article
Replacement product
Homomorphic product[1][3]
${\displaystyle G_{1}\ltimes G_{2}}$
${\displaystyle (u_{1}=v_{1})}$
or
${\displaystyle (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 ${\displaystyle K_{2}}$ be the complete graph on two vertices (i.e. a single edge). The product graphs ${\displaystyle K_{2}\square K_{2}}$, ${\displaystyle K_{2}\times K_{2}}$, and ${\displaystyle K_{2}\boxtimes K_{2}}$ look exactly like the graph representing the operator. For example, ${\displaystyle K_{2}\square K_{2}}$ is a four cycle (a square) and ${\displaystyle K_{2}\boxtimes K_{2}}$ is the complete graph on four vertices. The ${\displaystyle G_{1}[G_{2}]}$ notation for lexicographic product serves as a reminder that this product is not commutative.

## Notes

1. ^ a b Roberson, David E.; Mancinska, Laura (2012). "Graph Homomorphisms for Quantum Players". Journal of Combinatorial Theory, Series B. 118: 228–267. arXiv:1212.1724. doi:10.1016/j.jctb.2015.12.009.
2. ^ 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 978-3-540-60216-3.
3. ^ The hom-product of [2] is the graph complement of the homomorphic product of.[1]

## References

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