Graph operations

Operations on graphs produce new graphs from old ones. They may be separated into the following major categories.

Unary operations

Unary operations create a new graph from the old one.

Elementary operations

These are sometimes called "editing operations" on graphs. They create a new graph from the original one by a simple, local change, such as addition or deletion of a vertex or an edge, merging and splitting of vertices, edge contraction, etc.

Advanced operations

• Line graph
• Dual graph
• Complement graph
• Graph minor
• Power of graph: The k-th power G^k of a graph G is a supergraph formed by adding an edge between all pairs of vertices of G with distance at most k. The second power of a graph is also called its square.
• Mycielskian

Binary operations

Binary operations create a new graph from two initial graphs G1(V1, E1) and G2(V2, E2):

• The union of two graphs G = (V_G , E_G) and H = (V_H , E_H) is the union of their vertex and edge sets: G ∪ H = (V_G ∪ V_H, E_G ∪ E_H). When V_G and V_H are disjoint, their union is referred to as the disjoint union, and denoted G + H.^[1]
• Similarly to above, the intersection of two graphs G = (V_G , E_G) and H = (V_H , E_H) is G ∩ H = (V_G ∩ V_H, E_G ∩ E_H).^[1]
• The graph join (or complete join) of two graphs is their graph union with all the edges that connect the vertices of the first graph with the vertices of the second graph.^[2] It is a commutative operation (for unlabelled graphs)
• Graph products based on the Cartesian product of the vertex sets:
  • Cartesian product of graphs^[2] It is a commutative and associative operation (for unlabelled graphs).
  • Lexicographic product of graphs (also called graph composition) ^[2] It is associative (for unlabelled graphs), but not commutative.
  • Strong product of graphs; It is commutative and associative (for unlabelled graphs).
  • Tensor product of graphs, also called direct product, categorical product, cardinal product, or Kronecker product. It is a commutative and associative operation (for unlabelled graphs).
  • Zig-zag product of graphs ^[3] Let [N] denote the set of integers from 1 to N. It is supposed that k-regular graphs used in the definition below are k-edge colored, i.e., their edge sets are partitioned into k perfect matchings. For each color i and a vertex v let v[i] denote the neighbor of v along the edge colored with color i. Let G1 be a D1-regular graph on [N1] and let G2 be a D2-regular graph on [D1]. Then the zig-zag product H is a graph with vertex set [N1] × [D1], where for all n in [N1], d in [D1], and i,j, in [D2], the vertex (n, d) is connected to (n[d[i]], d[i][j]). This definition is used in construction of expander graphs.
• Other graph operations called "products"
  • Rooted product of graphs. It is noncommutative, but associative (for unlabelled but rooted graphs)
  • Corona product or simply corona of G1 and G2, defined by Frucht and Harary^[4] is the graph which is the disjoint union of one copy of G1 and |V1| copies of G2 (|V1| is the number of vertices of G1) in which each vertex of the copy of G1 is connected to all vertices of a separate copy of G2. Even for unlabelled graphs, it is neither commutative nor associative.
• Series-parallel graph creation:
  • Parallel composition. It is a commutative operation (for unlabelled graphs)
  • Series composition. Non-commutative
  • Source composition (source merge). It is a commutative operation (for unlabelled graphs)
• The Hajós construction

Notes

1. ↑ 1.0 1.1 Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics. Springer. p. 29. ISBN 978-1-84628-969-9. 
2. ↑ 2.0 2.1 2.2 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. doi:10.2307/3062153. JSTOR 3062153. MR 1888797. 
4. ↑ Robert Frucht and Frank Harary. "On the coronas of two graphs", Aequationes Math., 4:322–324, 1970.