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 a condition that takes into account the edges of G₁ and G₂. 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 somewhat 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 (Kronecker 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 (u₁, u₂) ∼ (v₁, v₂) that can be expressed in terms of the statements u₁ ∼ v₁, u₂ ∼ v₂, u₁ = v₁, and u₂ = v₂.

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.

See also

• Graph operations

Notes

1. 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}}CS1 maint: ref=harv (link).