# Graph operations > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_operations > Markdown URL: https://mediated.wiki/source/Graph_operations.md > Source: https://en.wikipedia.org/wiki/Graph_operations > Source revision: 1320808643 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Procedures for constructing new graphs in graph theory}} In the [mathematical](/source/mathematical) field of [graph theory](/source/graph_theory), '''graph operations''' are [operations](/source/Operation_(mathematics)) which produce new [graph](/source/Graph_(discrete_mathematics))s from initial ones. They include both [unary](/source/Unary_operation) (one input) and [binary](/source/Binary_operation) (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 {{anchor|Graph edit operations}}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](/source/edge_contraction), etc. The [graph edit distance](/source/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](/source/transpose_graph); * [complement graph](/source/complement_graph); * [line graph](/source/line_graph); * [graph minor](/source/graph_minor); * [graph rewriting](/source/graph_rewriting); * [power of graph](/source/power_of_graph); * [dual graph](/source/dual_graph); * [medial graph](/source/medial_graph); * [quotient graph](/source/quotient_graph); * [double graph](/source/double_graph); * [simplex graph](/source/simplex_graph); * [YΔ- and ΔY-transformation](/source/Y%CE%94-_and_%CE%94Y-transformation); * [Mycielskian](/source/Mycielskian). ==Binary operations== Binary operations create a new graph from two initial graphs {{nobreak|1=''G''1 = (''V''1, ''E''1)}} and {{nobreak|1=''G''2 = (''V''2, ''E''2)}}, such as: * graph union: {{nobreak|1=''G''1 ∪ ''G''2}}. There are two definitions. In the most common one, the [disjoint union of graphs](/source/disjoint_union_of_graphs), the union is assumed to be disjoint. Less commonly (though more consistent with the general definition of [union](/source/union_(set_theory)) in mathematics) the union of two graphs is defined as the graph {{nobreak|(''V''1 ∪ ''V''2, ''E''1 ∪ ''E''2)}}. * graph intersection: {{nobreak|1=''G''1 ∩ ''G''2 = (''V''1 ∩ ''V''2, ''E''1 ∩ ''E''2)}};{{cite book | last1 = Bondy | first1 = J. A. | last2 = Murty | first2 = U. S. R. | title = Graph Theory | publisher = Springer | series = Graduate Texts in Mathematics | date = 2008 | pages = 29 | isbn = 978-1-84628-969-9}} * [graph join](/source/join_(graph_theory)): 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); * [graph products](/source/graph_products) based on the [cartesian product](/source/cartesian_product) of the vertex sets: ** [cartesian graph product](/source/Cartesian_product_of_graphs): it is a commutative and associative operation (for unlabelled graphs),[Harary, F](/source/Frank_Harary). ''Graph Theory''. Reading, MA: Addison-Wesley, 1994. ** [lexicographic graph product](/source/Lexicographic_product_of_graphs) (or graph composition): it is an associative (for unlabelled graphs) and non-commutative operation, ** [strong graph product](/source/Strong_product_of_graphs): it is a commutative and associative operation (for unlabelled graphs), ** [tensor graph product](/source/Tensor_product_of_graphs) (or direct graph product, categorical graph product, cardinal graph product, Kronecker graph product): it is a commutative and associative operation (for unlabelled graphs), ** [replacement product](/source/replacement_product), ** [zig-zag graph product](/source/Zig-zag_product_of_graphs);{{cite journal |author1=Reingold, O. |author2=Vadhan, S. |author3=Wigderson, A. | title = Entropy waves, the zig-zag graph product, and new constant-degree expanders | journal = [Annals of Mathematics](/source/Annals_of_Mathematics) | volume = 155 | issue = 1 | year = 2002 | pages = 157–187 |mr=1888797 | doi = 10.2307/3062153 | jstor = 3062153|arxiv=math/0406038}} * graph product based on other products: ** [rooted graph product](/source/Rooted_product_of_graphs): it is an associative operation (for unlabelled but rooted graphs), ** [corona graph product](/source/Corona_product_of_graphs): it is a non-commutative operation;{{cite journal | last1 = Frucht | first1 = Robert | author-link = Robert Frucht | author-link2 = Frank Harary | last2 = Harary | first2 = Frank | year = 1970 | title = On the corona of two graphs | journal = [Aequationes Mathematicae](/source/Aequationes_Mathematicae) | volume = 4 | pages = 322–324 | doi=10.1007/bf01844162| hdl = 2027.42/44326 | hdl-access = free }} * [series–parallel graph composition](/source/Series%E2%80%93parallel_graph): ** 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](/source/Haj%C3%B3s_construction). ==Notes== {{DEFAULTSORT:Graph Operations}} Category:Graph operations --- Adapted from the Wikipedia article [Graph operations](https://en.wikipedia.org/wiki/Graph_operations) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_operations?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.