In

graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a graph product is a binary operation on graph
Graph may refer to:
Mathematics
* Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
* Graph (topology), a topological space resembling a graph in the sense of disc ...

s. Specifically, it is an operation that takes two graphs and and produces a graph with the following properties:
* The vertex set of is the Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\ti ...

, where and are the vertex sets of and , respectively.
* Two vertices and of are connected by an edge, iff
In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false.
The connective is bicondi ...

a condition about in and in is fulfilled.
The graph products differ in what exactly this condition is. It is always about whether or not the vertices in 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.
Overview table

The following table shows the most common graph products, with $\backslash sim$ denoting "is connected by an edge to", and $\backslash not\backslash sim$ denoting non-connection. 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 $(a\_1,\; a\_2)\; \backslash sim\; (b\_1,\; b\_2)$ that can be expressed in terms of $a\_n\; =\; b\_n$ and $a\_n\; \backslash sim\; b\_n$.Mnemonic

Let $K\_2$ be the complete graph on two vertices (i.e. a single edge). The product graphs $K\_2\; \backslash square\; K\_2$, $K\_2\; \backslash times\; K\_2$, and $K\_2\; \backslash boxtimes\; K\_2$ look exactly like the graph representing the operator. For example, $K\_2\; \backslash square\; K\_2$ is a four cycle (a square) and $K\_2\; \backslash boxtimes\; K\_2$ is the complete graph on four vertices. The $G\_1;\; href="/html/ALL/s/\_2.html"\; ;"title="\_2">\_2$See also

*Graph operations
In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations.
Unary operations
Unary operations create a new graph ...

Notes

References

* {{refend