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 disjoint union of graphs, sometimes referred to as simply graph union is defined as follows. For two graphs with disjoint vertex sets V1 and V2 (and hence disjoint edge sets), their disjoint union is the graph U(V1 ∪ V2, E1 ∪ E2).^[1] It is a commutative and associative operation (for unlabelled graphs).
• The graph 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.^[1] It is a commutative operation (for unlabelled graphs)
• Graph products based on the Cartesian product of the vertex sets:
  • Cartesian product of graphs ^[1] It is a commutative and associative operation (for unlabelled graphs).
  • Lexicographic product of graphs (also called graph composition) ^[1] It is noncommutative, non-associative
  • Strong product of graphs
  • Tensor product of graphs, also called direct product, categorical product, cardinal product, or Kronecker product. It is a commutative operation (for unlabelled graphs)
  • Zig-zag product of graphs ^[2] 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, non-associative
  • Corona product or simply corona of G1 and G2, defined by Frucht and Harary^[3] 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.
• Series-parallel graph creation:
  • Series composition. It is a commutative operation (for unlabelled graphs)
  • Parallel composition. Non-commutative
  • Source composition (source merge). It is a commutative operation (for unlabelled graphs)
• The Hajós construction

Notes

1. ^ ^{a b c d} Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.
2. ^ 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. MR1888797. 
3. ^ Robert Frucht and Frank Harary. "On the coronas of two graphs", Aequationes Math., 4:322–324, 1970.