Graph operations

Last updated August 17, 2024

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 G₁ = (V₁, E₁) and G₂ = (V₂, E₂), such as:

graph union: G₁ ∪ G₂. There are two definitions. In the most common one, the disjoint union of graphs, the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of union in mathematics) the union of two graphs is defined as the graph (V₁ ∪ V₂, E₁ ∪ E₂).
graph intersection: G₁ ∩ G₂ = (V₁ ∩ V₂, E₁ ∩ E₂);^[1]
graph join: $G_{1}\nabla G_{2}$ . 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

↑ Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9.
1 2 3 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. arXiv: math/0406038 . doi:10.2307/3062153. JSTOR 3062153. MR 1888797.
↑ Frucht, Robert; Harary, Frank (1970). "On the corona of two graphs". Aequationes Mathematicae . 4: 322–324. doi:10.1007/bf01844162. hdl: 2027.42/44326 .

Related Research Articles

In mathematics, a category is a collection of "objects" that are linked by "arrows". A category has two basic properties: the ability to compose the arrows associatively and the existence of an identity arrow for each object. A simple example is the category of sets, whose objects are sets and whose arrows are functions.

In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal.

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

<span class="mw-page-title-main">Graph (discrete mathematics)</span> Vertices connected in pairs by edges

In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called vertices and each of the related pairs of vertices is called an edge. Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices which, by most definitions, are all distinct. A directed path in a directed graph is a finite or infinite sequence of edges which joins a sequence of distinct vertices, but with the added restriction that the edges be all directed in the same direction.

In geometry, the 120-cell is the convex regular 4-polytope (four-dimensional analogue of a Platonic solid) with Schläfli symbol {5,3,3}. It is also called a C₁₂₀, dodecaplex (short for "dodecahedral complex"), hyperdodecahedron, polydodecahedron, hecatonicosachoron, dodecacontachoron and hecatonicosahedroid.

In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs.

<span class="mw-page-title-main">Cartesian product of graphs</span> Operation in graph theory

In graph theory, the Cartesian product $G □ H$ of graphs $G$ and $H$ is a graph such that:

In the mathematical field of graph theory, a path graph is a graph whose vertices can be listed in the order $v 1, v 2, ..., v n$ such that the edges are ${v i, v i +1$ } where $i = 1, 2, ..., n - 1$ . Equivalently, a path with at least two vertices is connected and has two terminal vertices, while all others have degree 2.

In the mathematical field of category theory, the product of two categories C and D, denoted C × D and called a product category, is an extension of the concept of the Cartesian product of two sets. Product categories are used to define bifunctors and multifunctors.

In computer graphics, a triangle mesh is a type of polygon mesh. It comprises a set of triangles that are connected by their common edges or vertices.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graph $Q n$ is the graph formed from the vertices and edges of an $n$ -dimensional hypercube. For instance, the cube graph $Q 3$ is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. $Q n$ has $2 n$ vertices, $2 n - 1 n$ edges, and is a regular graph with $n$ edges touching each vertex.

In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.

In graph theory, a graph product is a binary operation on graphs. Specifically, it is an operation that takes two graphs $G 1$ and $G 2$ and produces a graph $H$ with the following properties:

In the mathematical discipline of graph theory, a graph $C$ is a covering graph of another graph $G$ if there is a covering map from the vertex set of $C$ to the vertex set of $G$ . A covering map $f$ is a surjection and a local isomorphism: the neighbourhood of a vertex $v$ in $C$ is mapped bijectively onto the neighbourhood of ⁠ $⁠$ in $G$ .

In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph.

In geometry, a Hanner polytope is a convex polytope constructed recursively by Cartesian product and polar dual operations. Hanner polytopes are named after Olof Hanner, who introduced them in 1956.

In graph theory, a matching in a hypergraph is a set of hyperedges, in which every two hyperedges are disjoint. It is an extension of the notion of matching in a graph.

In graph theory, a balanced hypergraph is a hypergraph that has several properties analogous to that of a bipartite graph.

In graph theory, a rainbow-independent set (ISR) is an independent set in a graph, in which each vertex has a different color.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[bondy_murty-1] Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9.

[harary-2] 1 2 3 Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.

[3] 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. arXiv: math/0406038 . doi:10.2307/3062153. JSTOR 3062153. MR 1888797.

[4] Frucht, Robert; Harary, Frank (1970). "On the corona of two graphs". Aequationes Mathematicae . 4: 322–324. doi:10.1007/bf01844162. hdl: 2027.42/44326 .

[1]

[2]

[3]

[4]