Operations on Graphs

• We can usually use these operations to produce a proof by induction.

Graph Operations §

• The complement of , denoted is a graph such that and the following holds:

  • The complements of two isomorphic graphs are isomorphic. That is

• The Union of and , denoted is the graph where

• The Intersection of and , denoted is the graph where

• A graph decomposition is a list of edge-disjoint subgraphs. That is, if we have such that each are pairwise disjoint, then

  We denote this by saying

  analogous to direct sums

• Cartesian Product of Graphs

Edge Operations §

Edge Addition §

• Let be a graph and a set of edges. The graph obtained from edge addition is denoted and is the graph where all edges in are added to .

• If is singleton we denote this as
• Edge addition cannot increase the number of components.
  • Intuitively, this follows from the fact that adding an edge may connect two components together or it may not. In either case, we do not create any new components as a result.

Edge Contraction §

• An Edge Contraction is an operation that removes an edge while simultaneously merging and into a new vertex which is incident to all edges that were previously incident to either or
• The resulting graph is notated as . We say that is contractible to

Edge Deletion §

• If , then edge deletion is the operation of removing all edges in from . This is denoted
• If is singleton, then we denote this as

Edge Smoothing §

• Edge Smoothing is an operation on edges Consider a path contained in graph , where is adjacent to no other vertex.

  Delete vertex and connect and . Essentially, replace with the edge .

  More succinctly, it is the reverse operation of Edge Subdivision

Edge Subdivision §

• Let be an edge of . Edge subdivision involves deleting this edge and replacing it with a path of length by adding new edges .
• The Subdivision Graph of a graph , denoted is obtained by subdividing all edges.
  • The subdivision graph is bipartite, with the partitions corresponding to whether a vertex in belongs to or .
• If is -regular, then is a semiregular bipartite graph.

Vertex Operations §

• Let . The graph obtained from vertex deletion is denoted as and is the graph with all vertices and all incident edges from vertices in removed from .

  If is a singleton , we similarly denote the vertex deletion as .

Links §

• Fundamental Constructs of Graph Theory
• Algebraic Graph Theory by Godsil and Royle