Graph operations

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

Graph operations produce new graphs from initial ones. They may be separated into the following major categories.

Unary operations[edit]

Unary operations create a new graph from one initial one.

Elementary operations[edit]

Elementary operations or editing operations create a new graph from one initial one by a simple local change, such as addition or deletion of a vertex or of an edge, merging and splitting of vertices, edge contraction, etc. The graph edit distance between a pair of graphs is the minimum number of elementary operations required to transform one graph into the other.

Advanced operations[edit]

Advanced operations create a new graph from one initial one by a complex changes, such as:

Binary operations[edit]

Binary operations create a new graph from two initial ones G1 = (V1, E1) and G2 = (V2, E2), such as:

  • graph union: G1G2. There are two definitions. In the most common one, the disjoint union of graphs, the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of union in mathematics) the union of two graphs is defined as the graph (V1V2, E1E2).
  • graph intersection: G1G2 = (V1V2, E1E2);[1]
  • graph join: graph with all the edges that connect the vertices of the first graph with the vertices of the second graph. It is a commutative operation (for unlabelled graphs);[2]
  • graph products based on the cartesian product of the vertex sets:
  • graph product based on other products:
  • series-parallel graph composition:
    • parallel graph composition: it is a commutative operation (for unlabelled graphs),
    • series graph composition: it is a non-commutative operation,
    • source graph composition: it is a commutative operation (for unlabelled graphs);
  • Hajós construction.

Notes[edit]

  1. ^ Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9. 
  2. ^ a b c Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
  3. ^ Reingold, O.; Vadhan, S.; Wigderson, A. (2002). "Entropy waves, the zig-zag graph product, and new constant-degree expanders". Annals of Mathematics. 155 (1): 157–187. arXiv:math/0406038Freely accessible. doi:10.2307/3062153. JSTOR 3062153. MR 1888797. 
  4. ^ Frucht, Robert; Harary, Frank (1970). "On the corona of two graphs". Aequationes Mathematicae. 4: 322–324. doi:10.1007/bf01844162.