Operations on graphs produce new graph

Graph (mathematics)

In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...

s from old ones. They may be separated into the following major categories.

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

Edge contraction

In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging together the two vertices it previously connected. Edge contraction is a fundamental operation in the theory of graph minors...

, etc.

Advanced operations

• Line graph
  Line graph
  In graph theory, the line graph L of undirected graph G is another graph L that represents the adjacencies between edges of G...
  
  
• Dual graph
  Dual graph
  In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...
  
  
• Complement graph
  Complement graph
  In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
  
  
• Graph minor
• Power of graph: The k-th power G^k of a graph G is a supergraph
  Supergraph
  In mathematics and physics, the word supergraph has two main meanings:* In graph theory, if A is a subgraph of B, then B is said to be a supergraph of A...
  
   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
  Mycielskian
  In the mathematical area of graph theory, the Mycielskian or Mycielski graph of an undirected graph G is a graph μ formed from G by a construction of , who used it to show that there exist triangle-free graphs with arbitrarily large chromatic number.-Construction:Let the n vertices of the given...
  
  

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). 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. It is a commutative operation (for unlabelled graphs)
• Graph products based on the Cartesian product
  Cartesian product
  In mathematics, a Cartesian product is a construction to build a new set out of a number of given sets. Each member of the Cartesian product corresponds to the selection of one element each in every one of those sets...
  
   of the vertex sets:
  • Cartesian product of graphs
    Cartesian product of graphs
    In graph theory, the Cartesian product G \square H of graphs G and H is a graph such that* the vertex set of G \square H is the Cartesian product V × V; and...
    
      It is a commutative and associative operation (for unlabelled graphs).
  • Lexicographic product of graphs
    Lexicographic product of graphs
    In graph theory, the lexicographic product or graph composition of graphs and is a graph such that* the vertex set of is the cartesian product ; and...
    
     (also called graph composition) It is noncommutative, non-associative
  • Strong product of graphs
    Strong product of graphs
    In graph theory, the strong product G ⊠ H of graphs G and H is a graph such that* the vertex set of G ⊠ H is the Cartesian product V × V; and...
    
    
  • Tensor product of graphs
    Tensor product of graphs
    In graph theory, the tensor product G × H of graphs G and H is a graph such that* the vertex set of G × H is the Cartesian product V × V; and...
    
    , also called direct product, categorical product, cardinal product, or Kronecker product. It is a commutative operation (for unlabelled graphs)
  • Zig-zag product of graphs  Let [N] denote the set of integers from 1 to N. It is supposed that k-regular graph
    Regular graph
    In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
    
    s used in the definition below are k-edge colored
    Edge coloring
    In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
    
    , 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
    Regular graph
    In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
    
     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 graph
    Expander graph
    In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
    
    s.
• 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
    Robert Frucht
    Robert Wertheimer Frucht was a German-Chilean mathematician; his research specialty was graph theory and the symmetries of graphs....
    
     and Harary
    Frank Harary
    Frank Harary was a prolific American mathematician, who specialized in graph theory. He was widely recognized as one of the "fathers" of modern graph theory....
    
     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
  Series-parallel graph
  In graph theory, series-parallel graphs are graphs with two distinguished vertices called terminals, formed recursively by two simple composition operations. They can be used to model series and parallel electric circuits.-Definition and terminology:...
  
   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
  Hajós construction
  In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.-The construction:...