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 $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.

class="wikitable" style="text-align:center"
rowspan="2"\| Name !colspan="2"\| Condition for $(a_1, a_2) \sim (b_1, b_2)$ !rowspan="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}$ !rowspan="2"\| Example
! with $a_n ~\text{rel}~ b_n$ abbreviated as $\text{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$ \| 200px
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$ \| 200px
Lexicographical product $G_1 \cdot 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$ \| 200px
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_1^2 ~ 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$ \| 200px
Zig-zag product \| see article \| \| see article \| see article
Replacement product \| \| \| \|
Corona product \| \| \| \|
Homomorphic product{{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}}{{refn\|The hom-product of {{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}} is the graph complement of the homomorphic product of.}} $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)$ \|

class="wikitable" style="text-align:center"

rowspan="2"| Name

!colspan="2"| Condition for $(a_1, a_2) \sim (b_1, b_2)$

!rowspan="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}$

!rowspan="2"| Example

! with

a_n ~\text{rel}~ b_n

abbreviated as

\text{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$

| 200px

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$

| 200px

Lexicographical product

G_1 \cdot G_2

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$

| 200px

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_1^2 ~ 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$

| 200px

Zig-zag product

| see article

Replacement product

Corona product

Homomorphic product{{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}}{{refn|The hom-product of {{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}} is the graph complement of the homomorphic product of.}}

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 \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$ .

Notes

References

{{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}}

Graph product

Overview table

Mnemonic

See also

Notes

References