Complex Graph Operations

Introduction

This is the fourth article in the Graph Theory – Online Classes.

After learning the basic graph operations, its time to dive deeper and have some understanding about the complex operations which we can be done over a graph or a set of graphs. To learn about the basics you can always visit Graph Theory Basics.

Complex Graph Operations

Union of Graphs

The union of two graphs G(VG, EG) and H(VH, EH) is the union of their vertex sets and their edge families. Which means G ∪ H = (VG ∪ VH, EG ∪ EH).
The below image shows a union of graph G and graph H. Make sure that all the vertices and edges from both the graphs are present in the union. If possible draw it once yourself.
complex graph operations - union

Now there can be a special case in the union where the VG and VH are disjoint. In this case the Union is referred to as disjoint Union and it is denoted by G + H .

Below image shows how it looks.
DISJOINTUNION

Note that the vertex sets are disjoint in the two graphs.

Intersection of Graphs

The intersection of two graphs G(VG, EG) and H(VH, EH) is the union of their vertex sets and the intersection of their edge families. Which means G ∩ H = (VG ∪ VH, EG ∩ EH).

Below image demonstrate the Intersection of the two Graphs.
INTERSECTION
Notice that the vertex set is a union of both the vertex sets but the edge family consists only the edges which exist in both the graphs G and H.

Graph Join

Given two graphs G(VG, EG) and H(VH, EH), the join Graph will contain the union of the two graphs and all edges which can connect the vertices of G to vertices of H.

Below is an image to demonstrate that.

JOIN

Note that the join graph contains new edges ( which join the vertices of G to vertices of H ) apart from the disjoint union.

Difference of Graphs

Given two graphs G(VG, EG) and H(VH, EH), the difference Graph G – H will contain the union of the vertices of two graphs G and H and the edges in the difference is the difference of edges which is EG – EH

Few points

  • The Graph Difference of any graph and itself is an empty graph. Which means G – G = Empty Graph.
  • The vertices of the Graph Difference (G – H) are the union of the vertices of the graphs G and H
  • The edges of the Graph Difference (G – H) are the complement of the edges of the graphs G and H.
  • The Graph Difference (G – H) of two graphs has the same vertices as Graph Union (G ∪ H)
  • The Graph Difference (G – H) of two graphs has the same vertices as Graph Intersection G ∩ H

Below is an image to demonstrate the Graph Difference.
differenceunion of the two vertes

Note that the vertex set is the union of the two vertex sets where as the edges in the difference is the family of edges which are present in G but not in H.

Graph Complement

The complement of graph G(V, E) is a graph that has the same vertices as G but the edges defined by two vertices in the complement is adjacent only if they are not adjacent in G(V, E).

Few points

  • The Graph complement G’ is also called edge complement.
  • Vertex set is same for both G and G’.
  • Edges in G’ are not present in G.
  • The union of G and G’ is a complete graph.
  • The complement of a complete Graph is a Null Graph.

Below is a demonstration of Graph Complement.
complement

Note that the edges in G are not present in G’

Power Graph

The Power Graph of Graph G(V, E) is always calculated with respect to a constant k. Which means we will always say that the kth power of G and not just power of G. The kth power of G is a graph with the same set of vertices as G and an edge between two vertices in the Power Graph exists only if there is a path of length at most k between them.

Consider the below graph G(V, E), and lets say that we need to derive its square, which means the value of k is 2.
So the graph will result into the graph on the right.
power2
Note that the vertices 1 and 3 are connected because the there exists a path of length two or less in the original graph..
Similarly there exists paths of length two or less between {2, 4}, {3, 5}, {4, 1}, {5, 2 }, hence these vertices are connected in the power graph.

This concludes that all the graph are the first power of themselves. Which means if value of k is 1 then we get the same graph. And if the adjacency matrix of G is A then each cell (i,j) of A1 will give you the number of paths of length 1 between i and j.

Lets take another example. Again let the value of k is 2. Consider the graph below.
PWOER2_2
The edges {1,3}, {2,3}, {3,4}, {4,6}, {5,1} and {6,2} are connected because they have a path length of 2 or less between them in the original graph.
The edges {1,4}, {2,5} and {3,6} are not connected because the length of the path between them is three which is more than two.

We define a theorem which says that “when an adjacency matrix is raised to power k, then the element at index (i,j) of the matrix gives the total number of paths of length k between the vertices i and j”.

Let us validate this with the adjacency matrix of the above graph. Here is the adjacency matrix A and its square. Checking the values we see that index {1,3} and {1,5} has values 1 which means there are exactly one path of length two between {1,3} and {1,5} each. Also checking the values at index {1,1} or {2,2} or any diagonal element the values are 2 each, which means there are exactly two paths of length two from vertex 1 to itself or 2 to itself or so no.
adjacencypower
This also gives another theorem that the kth power of graph G can also be defined as the graph whose adjacency matrix is given by the sum of the first k powers of the adjacency matrix because it counts all path of lengths from 1 up to k.

Also, it can be proven that raising any graph to the power of its graph diameter gives a complete graph. I believe we didn’t discuss about the diameter of a graph. SO let us do the needful now.

“The diameter of a graph is the length of the shortest path between the most distanced nodes. It measures the extent of a graph and the topological length between two nodes.”

The complete graph is possible because the diameter is the longest path possible between the farthest nodes. This means that if we raise the graph to power of diameter, we will end up connecting all the vertices where the distance between them is less than or equal to diameter. Ideally that would be like connecting all the vertices with each other.

Let us validate this using the below graph, the length of the shortest path between the farthest nodes is three and so on.
So now in the graph at the right side we connect all the vertices where the path length is either 2 or 3.
DIAMETERPOWER

Line Graph

A line graph L(G) for a Graph G(V, E) is defined in a ways such that

  • Each vertex of L(G) represents an edge of G.
  • Two vertices of L(G) are adjacent if and only if their corresponding edges in G share a common endpoint.

Here is some more details on Line Graph if you want to read about it now.
Below is a demonstrations to the Line Graph.
linegraph
This is the introduction to Line Graphs. We will dedicate one full post to understand the usages of the Line Graph as it is very important.

We will close this post here. Hope you enjoyed reading. Don’t forget to subscribe to TechieMe to get updates on latest posts.

  • Gleb Abroskin

    Thanks for lessons. I have one question: why on picture describing graph complement there is no edge between right-bottom and right-top vertices?

    • Thanks for pointing that out! Its a mistake. There has to be one more edge in the graph. Total number of edges in a complete graph with 5 nodes is 10

      If the original graph has 4 edges then the complete must have 10 – 4 = 6 edges. I will update the image soon.