Graph operations produce new graphs from initial ones. They may be separated into the following major categories.
Unary operations create a new graph from one initial one.
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 create a new graph from one initial one by a complex changes, such as:
transpose graph;
complement graph;
line graph;
graph minor;
graph rewriting;
power of graph;
dual graph;
medial graph;
Y-Δ transform;
Mycielskian.
Binary operations create a new graph from two initial ones G1 = (V1, E1) and G2 = (V2, E2), such as:
graph union: G1 ∪ G2 = (V1 ∪ V2, E1 ∪ E2). When V1 and V2 are disjoint, the graph union is referred to as the disjoint graph union, and denoted G1 ⊕ G2;
graph intersection: G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2);
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);
graph products based on the cartesian product of the vertex sets:
cartesian graph product: it is a commutative and associative operation (for unlabelled graphs),
lexicographic graph product (or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation,
strong graph product: it is a commutative and associative operation (for unlabelled graphs),
tensor graph product (or direct graph product, categorical graph product, cardinal graph product, Kronecker graph product): it is a commutative and associative operation (for unlabelled graphs),
zig-zag graph product;
graph product based on other products:
rooted graph product: it is an associative operation (for unlabelled but rooted graphs),
corona graph product: it is a non-commutative operation;
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.
