Graph product

In graph theory, a '''graph product''' is a binary operation on graphs. Specifically, it is an operation that takes two graphs {{math|''G''{{sub|1}}}} and {{math|''G''{{sub|2}}}} and produces a graph {{mvar|H}} with the following properties: * The vertex set of {{mvar|H}} is the Cartesian product {{math|''V''(''G''{{sub|1}}) × ''V''(''G''{{sub|2}})}}, where {{math|''V''(''G''{{sub|1}})}} and {{math|''V''(''G''{{sub|2}})}} are the vertex sets of {{math|''G''{{sub|1}}}} and {{math|''G''{{sub|2}}}}, respectively. * Two vertices {{math|(''a''{{sub|1}},''a''{{sub|2}})}} and {{math|(''b''{{sub|1}},''b''{{sub|2}})}} of {{mvar|H}} are connected by an edge, iff a condition about {{math|''a''{{sub|1}}, ''b''{{sub|1}}}} in {{math|''G''{{sub|1}}}} and {{math|''a''{{sub|2}}, ''b''{{sub|2}}}} in {{math|''G''{{sub|2}}}} is fulfilled.

The graph products differ in what exactly this condition is. It is always about whether or not the vertices {{math|''a''{{sub|''n''}}, ''b''{{sub|''n''}}}} in {{mvar|G{{sub|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 <math>E=1</math>, and not <math>E=2</math> as the formula <math>E_{G\times H} = 2 E_{G} E_{H}</math> would suggest.

== Overview table == The following table shows the most common graph products, with <math>\sim</math> denoting "is connected by an edge to", and <math>\not\sim</math> denoting non-adjacency. While <math>\not\sim</math> ''does'' allow equality, <math>\not\simeq</math> means they must be distinct and non-adjacent. The operator symbols listed here are by no means standard, especially in older papers. {| class="wikitable" style="text-align:center" |- !rowspan="2"| Name !colspan="2"| Condition for <math>(a_1, a_2) \sim (b_1, b_2)</math> !rowspan="2"| Number of edges <math>\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}</math> !rowspan="2"| Example |- ! ! with <math>a_n ~\text{rel}~ b_n</math> abbreviated as <math>\text{rel}_n</math> |- | Cartesian product (box product) <math>G_1 \square G_2</math> | <math>a_1 = b_1 ~\land~ a_2 \sim b_2</math> <math>\lor</math> <math>a_1 \sim b_1 ~\land~ a_2 = b_2</math> | <math>=_1 ~ \sim_2</math> <math>\lor</math> <math>\sim_1 ~ =_2</math> | <math>v_1 ~ e_2 ~+~ e_1 ~ v_2</math> | 200px |- | Tensor product (Kronecker product, categorical product) <math>G_1 \times G_2</math> | <math>a_1 \sim b_1 ~\land~ a_2 \sim b_2</math> | <math>\sim_1 ~ \sim_2</math> | <math>2 ~ e_1 ~ e_2</math> | 200px |- | Strong product (Normal product, AND product) <math>G_1 \boxtimes G_2</math> <math>= (G_1 \times G_2) \cup (G_1 \square G_2)</math> | <math>a_1 = b_1 ~\land~ a_2 \sim b_2</math> <math>\lor</math> <math>a_1 \sim b_1 ~\land~ a_2 = b_2</math> <math>\lor</math> <math>a_1 \sim b_1 ~\land~ a_2 \sim b_2</math> | <math>=_1 ~ \sim_2</math> <math>\lor</math> <math>\sim_1 ~ =_2</math> <math>\lor</math> <math>\sim_1 ~ \sim_2</math> | <math>v_1 ~ e_2 ~+~ e_1 ~ v_2 ~+~ 2 ~ e_1 ~ e_2</math> | |- | Lexicographical product <math>G_1 \cdot G_2</math> or <math>G_1[G_2]</math> | <math>a_1 \sim b_1</math> <math>\lor</math> <math>a_1 = b_1 ~\land~ a_2 \sim b_2</math> | <math>\sim_1</math> <math>\lor</math> <math>=_1 ~ \sim_2</math> | <math>v_1 ~ e_2 ~+~ e_1 ~ v_2^2</math> | 200px |- | Co-normal product (disjunctive product,<ref>[https://arxiv.org/pdf/1212.4129 Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More], Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, 2012</ref> OR product) <math>G_1 * G_2</math> or <math>G_1 \lor G_2</math> <math>= G_1[G_2] \cup G_2[G_1]</math> <math>= \overline{\;\overline{G_1}\boxtimes\overline{G_2}\;}</math> | <math>a_1 \sim b_1</math> <math>\lor</math> <math>a_2 \sim b_2</math> | <math>\sim_1</math> <math>\lor</math> <math>\sim_2</math> | <math>v_1^2 ~ e_2 ~+~ e_1 ~ v_2^2 ~-~ 2 ~ e_1 ~ e_2</math> | |- | Modular product <math>G_1 \diamond G_2</math> <math> = (G_1 \boxtimes G_2) \cup (\overline{G_1} \times \overline{G_2})</math> | <math>a_1 \sim b_1 ~\land~ a_2 \sim b_2</math> <math>\lor</math> <math>a_1 \not\simeq b_1 ~\land~ a_2 \not\simeq b_2</math> | <math>\sim_1 ~ \sim_2</math> <math>\lor</math> <math>\not\simeq_1 ~ \not\simeq_2</math> | | |- | Rooted product | see article | | <math>v_1 ~ e_2 ~+~ e_1</math> | 200px |- | Zig-zag product | see article | | see article | see article |- | Replacement product | | | | |- | Homomorphic product<ref name=rm12>{{cite journal |arxiv=1212.1724|last1= Roberson|first1= David E.|title= Graph Homomorphisms for Quantum Players|last2= Mancinska|first2= Laura|year= 2012|doi=10.1016/j.jctb.2015.12.009|volume=118|journal=Journal of Combinatorial Theory, Series B|pages=228–267}}</ref>{{refn|The hom-product of <ref>{{Cite book | doi = 10.1007/BFb0030878| chapter = Semidefinite programming and its applications to NP problems| title = Computing and Combinatorics| volume = 959| pages = 566| series = Lecture Notes in Computer Science| year = 1995| last1 = Bačík | first1 = R. | last2 = Mahajan | first2 = S. | isbn = 978-3-540-60216-3}}</ref> is the graph complement of the homomorphic product of.<ref name=rm12/>}} <math>G_1 \ltimes G_2</math> | <math>a_1 = b_1</math> <math>\lor</math> <math>a_1 \sim b_1 ~\land~ a_2 \not\sim b_2</math> | <math>=_1</math> <math>\lor</math> <math>\sim_1 ~ \not\sim_2</math> | <math>v_1 v_2 (v_2 - 1) / 2 + e_1 (v_2^2 - 2 e_2)</math> | |}

In general, a graph product is determined by any condition for <math>(a_1, a_2) \sim (b_1, b_2)</math> that can be expressed in terms of <math>a_n = b_n</math> and <math>a_n \sim b_n</math>.

==Mnemonic==

Let <math>K_2</math> be the complete graph on two vertices (i.e. a single edge). The product graphs <math>K_2 \square K_2</math>, <math>K_2 \times K_2</math>, and <math>K_2 \boxtimes K_2</math> look exactly like the graph representing the operator. For example, <math>K_2 \square K_2</math> is a four cycle (a square) and <math>K_2 \boxtimes K_2</math> is the complete graph on four vertices.

The <math>G_1[G_2]</math> notation for lexicographic product serves as a reminder that this product is not commutative. The resulting graph looks like substituting a copy of <math>G_2</math> for every vertex of <math>G_1</math>.

==See also== * Graph operations

==Notes==

==References==

{{refbegin}} * {{Cite book| last1 = Imrich | first1 = Wilfried | last2 = Klavžar | first2 = Sandi | title = Product Graphs: Structure and Recognition | publisher = Wiley | year = 2000 | isbn = 978-0-471-37039-0}} {{refend}} * {{MathWorld|GraphProduct|Graph Product}} * {{MathWorld|GraphCartesianProduct|Graph Cartesian Product}} * {{MathWorld|GraphTensorProduct|Graph Tensor Product}} * {{MathWorld|GraphStrongProduct|Graph Strong Product}} * {{MathWorld|GraphLexicographicProduct|Graph Lexicographic Product}}

Category:Graph products