Graph (mathematics) - Operations On Graphs

Operations On Graphs

There are several operations that produce new graphs from old ones, which might be classified into the following categories:

• Elementary operations, sometimes called "editing operations" on graphs, which 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, etc.
• Graph rewrite operations replacing the occurrence of some pattern graph within the host graph by an instance of the corresponding replacement graph.
• Unary operations, which create a significantly new graph from the old one. Examples:
  • Line graph
  • Dual graph
  • Complement graph
• Binary operations, which create new graph from two initial graphs. Examples:
  • Disjoint union of graphs
  • Cartesian product of graphs
  • Tensor product of graphs
  • Strong product of graphs
  • Lexicographic product of graphs