In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs G1 and G2 and produces a graph H with the following properties:
- The vertex set of H is the Cartesian product V(G1) × V(G2), where V(G1) and V(G2) are the vertex sets of G1 and G2, respectively.
- Two vertices (a1,a2) and (b1,b2) of H are connected by an edge, iff a condition about a1, b1 in G1 and a2, b2 in G2 is fulfilled.
The graph products differ in what exactly this condition is. It is always about whether or not the vertices an, bn in Gn 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\times H} = 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\mathrm{V}(G_1)\vert & v_2 = \vert\mathrm{V}(G_2)\vert \\ e_1 = \vert\mathrm{E}(G_1)\vert & e_2 = \vert\mathrm{E}(G_2)\vert \end{array} | Example | |
|---|---|---|---|---|
with a_n ~\text{rel}~ b_nabbreviated as \text{rel}_n | ||||
| Cartesian product (box product) G_1 \square G_2 | a_1 = b_1 ~\land~ a_2 \sim b_2\lora_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 \times G_2 | a_1 \sim b_1 ~\land~ a_2 \sim b_2 | \sim_1 ~ \sim_2 | 2 ~ e_1 ~ e_2 | |
| Strong product (Normal product, AND product) G_1 \boxtimes G_2= (G_1 \times G_2) \cup (G_1 \square G_2) | a_1 = b_1 ~\land~ a_2 \sim b_2\lora_1 \sim b_1 ~\land~ a_2 = b_2\lora_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 | |
Lexicographical productG_1 \cdot G_2 or G_1[G_2] | a_1 \sim b_1\lora_1 = b_1 ~\land~ a_2 \sim b_2 | \sim_1\lor=_1 ~ \sim_2 | v_1 ~ e_2 ~+~ e_1 ~ v_2^2 | |
| Co-normal product (disjunctive product,[1] OR product) G_1 * G_2 or G_1 \lor G_2 = G_1[G_2] \cup G_2[G_1]= \overline{\;\overline{G_1}\boxtimes\overline{G_2}\;} | a_1 \sim b_1\lora_2 \sim b_2 | \sim_1\lor\sim_2 | v_1^2 ~ e_2 ~+~ e_1 ~ v_2^2 ~-~ 2 ~ e_1 ~ e_2 | |
Modular productG_1 \diamond G_2= (G_1 \boxtimes G_2) \cup (\overline{G_1} \times \overline{G_2}) | a_1 \sim b_1 ~\land~ a_2 \sim b_2\lora_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[2][3]G_1 \ltimes G_2 | a_1 = b_1\lora_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 \times 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
Notes
- ^ Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, 2012
- ^ 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
- ^ The hom-product of [4] is the graph complement of the homomorphic product of.[2]
- ^ Bačík, R. & Mahajan, S. (1995). "Semidefinite programming and its applications to NP problems". Computing and Combinatorics. Vol. 959. Lecture Notes in Computer Science. p. 566. doi:10.1007/BFb0030878. ISBN 978-3-540-60216-3.
References
- Imrich, Wilfried & Klavžar, Sandi (2000). Product Graphs: Structure and Recognition. Wiley. ISBN 978-0-471-37039-0.