Graph operations
From Infogalactic: the planetary knowledge core
(Redirected from Disjoint union of graphs)
Graph operations produce new graphs from initial ones. They may be separated into the following major categories.
Contents
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. 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 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), 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;[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
- ↑ 1.0 1.1 Lua error in package.lua at line 80: module 'strict' not found.
- ↑ 2.0 2.1 2.2 Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
- ↑ Lua error in package.lua at line 80: module 'strict' not found.
- ↑ Robert Frucht and Frank Harary. "On the coronas of two graphs", Aequationes Math., 4:322–324, 1970.
