Graph product

In graph theory, 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 (a₁,a₂) and (b₁,b₂) of H are connected by an edge, iff a condition about a₁, b₁ in G₁ and a₂, b₂ in G₂ 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 in G_n 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 ${\displaystyle E=1}$, and not ${\displaystyle E=2}$ as the formula ${\displaystyle E_{G\times H}=2E_{G}E_{H}}$ would suggest.

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-adjacency. While ${\displaystyle \not \sim }$ does allow equality, ${\displaystyle \not \simeq }$ means they must be distinct and non-adjacent. The operator symbols listed here are by no means standard, especially in older papers.

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

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. The resulting graph looks like substituting a copy of ${\displaystyle G_{2}}$ for every vertex of ${\displaystyle G_{1}}$.

See also

• Graph operations

Notes

References