Graph product

Template:Short description

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) \times 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.

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 $\sim̸$ denoting non-adjacency. While $\sim̸$ does allow equality, $≄$ 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{matrix} v_{1} = \| V (G_{1}) \| & v_{2} = \| V (G_{2}) \| \\ e_{1} = \| E (G_{1}) \| & e_{2} = \| E (G_{2}) \| \end{matrix}$	Example
Name		with $a_{n} rel b_{n}$ abbreviated as ${rel}_{n}$		Example
Cartesian product (box product) $G_{1} ◻ 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} \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} ⊠ G_{2}$ $= (G_{1} \times G_{2}) \cup (G_{1} ◻ 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}$
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}$
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}} ⊠ \overline{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 $G_{1} ⋄ G_{2}$ $= (G_{1} ⊠ G_{2}) \cup (\overline{G_{1}} \times \overline{G_{2}})$	$a_{1} \sim b_{1} \land a_{2} \sim b_{2}$ $\lor$ $a_{1} ≄ b_{1} \land a_{2} ≄ b_{2}$	$\sim_{1} \sim_{2}$ $\lor$ $≃_{1} ≃_{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]^[4] $G_{1} ⋉ G_{2}$	$a_{1} = b_{1}$ $\lor$ $a_{1} \sim b_{1} \land a_{2} \sim̸ b_{2}$	$=_{1}$ $\lor$ $\sim_{1} \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} ◻ K_{2}$ , $K_{2} \times K_{2}$ , and $K_{2} ⊠ K_{2}$ look exactly like the graph representing the operator. For example, $K_{2} ◻ K_{2}$ is a four cycle (a square) and $K_{2} ⊠ 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

Page Template:Reflist/styles.css has no content.

^ Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, 2012
^ ^a ^b Page Module:Citation/CS1/styles.css has no content.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.
^ Page Module:Citation/CS1/styles.css has no content.Bačík, R.; Mahajan, S. (1995). "Semidefinite programming and its applications to NP problems". Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 959. p. 566. doi:10.1007/BFb0030878. ISBN 978-3-540-60216-3.
^ The hom-product of ^[3] is the graph complement of the homomorphic product of.^[2]

References

Page Template:Refbegin/styles.css has no content.

Page Module:Citation/CS1/styles.css has no content.Imrich, Wilfried; Klavžar, Sandi (2000). Product Graphs: Structure and Recognition. Wiley. ISBN 978-0-471-37039-0.

Script error: No such module "Template wrapper".
Script error: No such module "Template wrapper".
Script error: No such module "Template wrapper".
Script error: No such module "Template wrapper".
Script error: No such module "Template wrapper".

[1] Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, 2012

[rm12-2] Page Module:Citation/CS1/styles.css has no content.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.

[3] Page Module:Citation/CS1/styles.css has no content.Bačík, R.; Mahajan, S. (1995). "Semidefinite programming and its applications to NP problems". Computing and Combinatorics. Lecture Notes in Computer Science. Vol. 959. p. 566. doi:10.1007/BFb0030878. ISBN 978-3-540-60216-3.

[4] The hom-product of ^[3] is the graph complement of the homomorphic product of.^[2]

[1]

[2]

[4]

[3]

Anonymous

Search

Graph product

Namespaces

More

Page actions

Contents

Overview table

Mnemonic

See also

Notes

References

Navigation

Navigation

Contribute

Wiki tools

Wiki tools

Anonymous

Search

Graph product

Overview table

Mnemonic

See also

Notes

References

Navigation

Wiki tools

Page tools

Categories