Graph operations explained

In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary (one input) and binary (two input) operations.

Unary operations

Unary operations create a new graph from a single initial graph.

Elementary operations

Elementary operations or editing operations, which are also known as graph edit 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

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

Binary operations

Binary operations create a new graph from two initial graphs and, such as:

G1\nablaG2

. 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);

Notes

  1. Book: Bondy . J. A. . Murty . U. S. R. . Graph Theory . Springer . Graduate Texts in Mathematics . 2008 . 29 . 978-1-84628-969-9.
  2. [Frank Harary|Harary, F]
  3. Reingold, O. . Vadhan, S. . Wigderson, A. . Entropy waves, the zig-zag graph product, and new constant-degree expanders . . 155 . 1 . 2002 . 157–187 . 1888797 . 10.2307/3062153 . 3062153. math/0406038.
  4. Frucht . Robert . Robert Frucht . Frank Harary . Harary . Frank . 1970 . On the corona of two graphs . . 4 . 322–324 . 10.1007/bf01844162. 2027.42/44326 . free .