Graph product

From Wikipedia, the free encyclopedia

A graph product is a binary operation on graphs. There are several similarly defined operations on graphs, called "product". Given two graphs G1 and G2, their product H is a graph such that

  • the vertex set of H is the Cartesian product V(G_1) \times V(G_2), i.e., the set of ordered pairs (v1, v2), with v1 being a vertex of G1 and v2 being a vertex of G2; and
  • two vertices (u1, u2) and (v1, v2) of H are adjacent if and only if the certain conditions expressed in terms of adjacency or equality of u1 and u2 and those of v1 and v2 are satisfied.

The following graph products are most common.

  1. Condition 1 defines the Cartesian product of graphs: ( u1=v1 and (u2, v2) is an edge of G2 ) or ( u2=v2 and (u1, v1) is an edge of G1 )
  2. Condition 2 defines the Tensor product of graphs: (u1, v1) is an edge of G1 and (u2, v2) is an edge of G2
  3. Condition 3 defines the Lexicographical product of graphs: (u1, v1) is an edge of G1 or ( u1=v1 and (u2, v2) is an edge of G2 )
  4. Condition 4 defines the Normal product of graphs ("strong product", "AND product"): ( u1=v1 and (u2, v2) is an edge of G2 ) or ( u2=v2 and (u1, v1) is an edge of G1 ) or ( (u1, v1) is an edge of G1 and (u2, v2) is an edge of G2 ).
  5. Condition 5 defines the Co-normal product of graphs ("disjunctive product" or "OR product"): (u1, v1) is an edge of G1 or (u2, v2) is an edge of G2

Some other operations are also called "product", such as rooted product of graphs.

[edit] References

  • Golumbic, Martin Charles & Rotics, Udi (2000), “On the clique-width of some perfect graph classes”, International Journal of Foundations of Computer Science 11 (3): 423–443 .
  • Imrich, Wilfried & Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8 .
Languages