Graph product

In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G_1 and G_2 and produces a graph H with the following properties: The vertex set of H is the Cartesian product V(G_1) × V(G_2), where V(G_1) and V(G_2) are the vertex sets of G_1 and G_2, respectively. Two vertices (a_1,a_2) and (b_1,b_2) of H are connected by an edge, iff a condition about a_1, b_1 in G_1 and a_2, b_2 in G_2 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. The following table shows the most common graph products, with denoting "is connected by an edge to", and 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 that can be expressed in terms of and . Let be the complete graph on two vertices (i.e. a single edge). The product graphs , , and look exactly like the graph representing the operator. For example, is a four cycle (a square) and is the complete graph on four vertices. The notation for lexicographic product serves as a reminder that this product is not commutative. The resulting graph looks like substituting a copy of for every vertex of .