Graph operations
In the mathematical field of graph theory, graph operations are operations which produce new graphs from initial ones. They include both unary and binary 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:- transpose graph;
- complement graph;
- line graph;
- graph minor;
- graph rewriting;
- power of graph;
- dual graph;
- medial graph;
- quotient graph;
- double graph;
- simplex graph;
- YΔ- and ΔY-transformation;
- Mycielskian.
Binary operations
Binary operations create a new graph from two initial graphs and, such as:- graph union:. There are two definitions. In the most common one, the union of graphs">union (set theory)">union of graphs, the union is assumed to be disjoint. Less commonly the union of two graphs is defined as the graph.
- graph intersection: ;
- 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 ;
- graph products based on the cartesian product of the vertex sets:
- * Cartesian [product of graphs|cartesian graph product]: it is a commutative and associative operation,
- * lexicographic graph product : it is an associative and non-commutative operation,
- * strong graph product: it is a commutative and associative operation,
- * tensor graph product : it is a commutative and associative operation,
- * replacement product,
- * zig-zag graph product;
- graph product based on other products:
- * rooted graph product: it is an associative operation,
- * corona graph product: it is a non-commutative operation;
- series–parallel graph composition:
- * parallel graph composition: it is a commutative operation,
- * series graph composition: it is a non-commutative operation,
- * source graph composition: it is a commutative operation ;
- Hajós construction.