Graph product

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, 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 (a1a2) and (b1b2) 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.

Overview table[edit]

The following table shows the most common graph products, with denoting “is connected by an edge to”, and denoting non-connection. The operator symbols listed here are by no means standard, especially in older papers.

Name Condition for Number of edges
Example
with
abbreviated as
Cartesian product




Graph-Cartesian-product.svg
Tensor product
(Kronecker product,
categorical product)
Graph-tensor-product.svg
Lexicographical product
or




Graph-lexicographic-product.svg
Strong product
(Normal product,
AND product)








Co-normal product
(disjunctive product, OR product)




Modular product



Rooted product see article Graph-rooted-product.svg
Zig-zag product see article see article see article
Replacement product
Homomorphic product[1][3]




In general, a graph product is determined by any condition for that can be expressed in terms of and .


Mnemonic[edit]

Let be the complete graph on two vertices (i.e. a single edge). The product graphs , , and look exactly like the graph representing the operator. For example, is a four cycle (a square) and is the complete graph on four vertices. The notation for lexicographic product serves as a reminder that this product is not commutative.

See also[edit]

Notes[edit]

  1. ^ a b 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.
  2. ^ Bačík, R.; Mahajan, S. (1995). "Semidefinite programming and its applications to NP problems". Computing and Combinatorics. Lecture Notes in Computer Science. 959. p. 566. doi:10.1007/BFb0030878. ISBN 978-3-540-60216-3.
  3. ^ The hom-product of [2] is the graph complement of the homomorphic product of.[1]

References[edit]

  • Imrich, Wilfried; Klavžar, Sandi (2000). Product Graphs: Structure and Recognition. Wiley. ISBN 978-0-471-37039-0{{inconsistent citations}}CS1 maint: postscript (link).