Graph operations
Graph operations produce new graphs from initial ones. They may be separated into the following major categories.
Unary operations
Unary operations create a new graph from one initial one.
Elementary operations
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.
Advanced operations
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
Binary operations create a new graph from two initial ones G1 = (V1, E1) and G2 = (V2, E2):
- 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.[1]
- Graph intersection: G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2).[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:
- Cartesian graph product: it is a commutative and associative operation (for unlabelled graphs).[2]
- Lexicographic graph product (or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation.[2]
- 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.[3]
- 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.[4]
- 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
- ^ a b Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9.
- ^ a b c Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
- ^ 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. doi:10.2307/3062153. JSTOR 3062153. MR 1888797.
{{cite journal}}: CS1 maint: multiple names: authors list (link) - ^ Robert Frucht and Frank Harary. "On the coronas of two graphs", Aequationes Math., 4:322–324, 1970.