Graph product

Graph product

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) imes 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.
#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 ).
#Condition 2 defines the Tensor product of graphs: (u1, v1) is an edge of G1 and (u2, v2) is an edge of G2.
#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 ).
#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 ).
#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.

References

*citation
last1 = Imrich | first1 = Wilfried
last2 = Klavžar | first2 = Sandi
title = Product Graphs: Structure and Recognition
publisher = Wiley
year = 2000
id = ISBN 0-471-37039-8.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать курсовую

Look at other dictionaries:

  • Graph operations — Operations on graphs produce new graphs from old ones. They may be separated into the following major categories. Contents 1 Unary operations 1.1 Elementary operations 1.2 Advanced operations 2 …   Wikipedia

  • Product naming — is the discipline of deciding what a product will be called, and is very similar in concept and approach to the process of deciding on a name for a company or organization. Product naming is considered a critical part of the branding process,… …   Wikipedia

  • product breakdown structure — UK US noun [C] (ABBREVIATION PBS) GRAPHS & CHARTS ► a graph used in planning a project to show how the different parts of it relate to each other …   Financial and business terms

  • Graph (mathematics) — This article is about sets of vertices connected by edges. For graphs of mathematical functions, see Graph of a function. For statistical graphs, see Chart. Further information: Graph theory A drawing of a labeled graph on 6 vertices and 7 edges …   Wikipedia

  • Graph of groups — In geometric group theory, a graph of groups is an object consisting of a collection of groups indexed by the vertices and edges of a graph, together with a family of injective homomorphisms of the edge groups into the vertex groups.There is a… …   Wikipedia

  • Graph homomorphism — Not to be confused with graph homeomorphism. In the mathematical field of graph theory a graph homomorphism is a mapping between two graphs that respects their structure. More concretely it maps adjacent vertices to adjacent vertices. Contents 1… …   Wikipedia

  • -graph — comb. form forming nouns and verbs meaning: 1 a thing written or drawn etc. in a specified way (autograph; photograph). 2 an instrument that records (heliograph; seismograph; telegraph). * * * ˌgraf, aa(ə)f, aif, ȧf noun combining form ( s)… …   Useful english dictionary

  • -graph — a combining form meaning drawn, written (lithograph; monograph); specialized in meaning to indicate the instrument rather than the written product of the instrument (telegraph; phonograph). [ < Gk graphos (something) drawn or written, one who… …   Universalium

  • Rooted product of graphs — In mathematical graph theory, the rooted product of a graph G and a rooted graph H is defined as follows: take | V ( G )| copies of H , and for every vertex v i of G , identify v i with the root node of the i th copy of H .More formally, assuming …   Wikipedia

  • Distance-regular graph — Graph families defined by their automorphisms distance transitive distance regular strongly regular …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”