Graph product explained

In graph theory, a graph product is a binary operation on graphs. 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, where and are the vertex sets of and, respectively.
• Two vertices and of are connected by an edge, iff 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.

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

E =1 , and not E =2 as the formula E _{G x} = 2 E _{G} E _{H} would suggest.

Overview table

The following table shows the most common graph products, with

\sim denoting "is connected by an edge to", and \not\sim denoting non-adjacency. While \not\sim does allow equality, \not\simeq means they must be distinct and non-adjacent. The operator symbols listed here are by no means standard, especially in older papers.

Name	Condition for (a _{1,} a _{2)} \sim (b _{1,} b _{2)}		Number of edges \begin{array}{cc} v _{1} = \vert V (G _{1)\vert} & v _{2} = \vert V (G _{2)\vert} \ e _{1} = \vert E (G _{1)\vert} & e _{2} = \vert E (G _{2)\vert} \end{array}	Example
		with a _{n} ~ rel ~ b _{n} abbreviated as rel _{n}
Cartesian product (box product) G _{1} \square G _{2}	a _{1} = b _{1} ~\land~ a _{2} \sim b _{2} \lor a _{1} \sim b _{1} ~\land~ a _{2} = b _{2}	= _{1} ~ \sim _{2} \lor \sim _{1} ~ = _{2}	v _{1} ~ e _{2} ~ + ~ e _{1} ~ v _{2}
Tensor product (Kronecker product, categorical product) G _{1} x G _{2}	a _{1} \sim b _{1} ~\land~ a _{2} \sim b _{2}	\sim _{1} ~ \sim _{2}	2 ~ e _{1} ~ e _{2}
Lexicographical product G _{1} ⋅ G _{2} or G _{1[G} _{2]}	a _{1} \sim b _{1} \lor a _{1} = b _{1} ~\land~ a _{2} \sim b _{2}	\sim _{1} \lor = _{1} ~ \sim _{2}	v _{1} ~ e _{2} ~ + ~ e _{1} ~ v ^{2} _{2}
Strong product (Normal product, AND product) G _{1} \boxtimes G _{2}	a _{1} = b _{1} ~\land~ a _{2} \sim b _{2} \lor a _{1} \sim b _{1} ~\land~ a _{2} = b _{2} \lor a _{1} \sim b _{1} ~\land~ a _{2} \sim b _{2}	= _{1} ~ \sim _{2} \lor \sim _{1} ~ = _{2} \lor \sim _{1} ~ \sim _{2}	v _{1} ~ e _{2} ~ + ~ e _{1} ~ v _{2} ~ + ~ 2 ~ e _{1} ~ e _{2}
Co-normal product (disjunctive product, OR product) G _{1} * G _{2}	a _{1} \sim b _{1} \lor a _{2} \sim b _{2}	\sim _{1} \lor \sim _{2}	v ^{2} _{1} ~ e _{2} ~ + ~ e _{1} ~ v ^{2} _{2} ~ - ~ 2 ~ e _{1} ~ e _{2}
Modular product	a _{1} \sim b _{1} ~\land~ a _{2} \sim b _{2} \lor a _{1} \not\simeq b _{1} ~\land~ a _{2} \not\simeq b _{2}	\sim _{1} ~ \sim _{2} \lor \not\simeq _{1} ~ \not\simeq _{2}
Rooted product	see article		v _{1} ~ e _{2} ~ + ~ e _{1}
Zig-zag product	see article		see article	see article
Replacement product
Homomorphic product^[1] G _{1} \ltimes G _{2}	a _{1} = b _{1} \lor a _{1} \sim b _{1} ~\land~ a _{2} \not\sim b _{2}	= _{1} \lor \sim _{1} ~ \not\sim _{2}	v _{1} v _{2} (v _{2} - 1 ) / 2 + e _{1} (v ^{2} _{2} - 2 e _{2)}

In general, a graph product is determined by any condition for

(a _{1,} a _{2)} \sim (b _{1,} b _{2)} that can be expressed in terms of a _{n} = b _{n} and a _{n} \sim b _{n} .

Mnemonic

Let

K _{2} be the complete graph on two vertices (i.e. a single edge). The product graphs K _{2} \square K _{2} , K _{2} x K _{2} , and K _{2} \boxtimes K _{2} look exactly like the graph representing the operator. For example, K _{2} \square K _{2} is a four cycle (a square) and K _{2} \boxtimes K _{2} is the complete graph on four vertices.

The

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 G _{2} for every vertex of G _{1} .

See also

• Graph operations

References

• Book: Imrich . Wilfried . Klavžar . Sandi . Product Graphs: Structure and Recognition . Wiley . 2000 . 978-0-471-37039-0.

Notes and References

1. 1212.1724. Roberson. David E.. Graph Homomorphisms for Quantum Players. Mancinska. Laura. 2012. 10.1016/j.jctb.2015.12.009. 118. Journal of Combinatorial Theory, Series B. 228–267.