Special Graphs

Introduction

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

Dear readers, I assume that you have already finished reading the first post, if not I would advise you to please go through the first article in the series Introduction to Graph Theory, as this post will require some basic knowledge which we discussed in the previous post.

Few Special Graphs

The Null Graph

The first graph we will discuss is the Null Graph. By definition, this graph has a V(G) which is non-empty and a E(G) which is empty. In simple words a graph which only has vertices and no edges is a Null Graph.

Few points about Null Graph.

  • A Null Graph is represented using the symbol Nn where n is the number of vertices.
  • In a Null Graph, every vertex is isolated.
  • A Nn is always a totally disconnected graph if n is greater than 1.
  • Number of vertices in such a graph is always n.
  • Number of edges in such a graph is always zero.

The Graph 1 in the below image is a Null Graph N4.
special graphs
The Complete Graph

For a simple graph to be a complete graph, it is important that every pair of its distinct vertices are adjacent to each other. In simple words, each vertex is connected to the remaining vertices.

Few points about Complete Graph.

  • A Complete Graph is represented using the symbol Kn where n is the number of vertices.
  • In a Complete Graph, every vertex is connected to every other vertex, which means in Kn every vertex is connected to n-1 vertices, this also means that there are n-1 edges connected to each vertex.
  • Number of vertices in such a graph is always n.
  • Number of edges in such a graph is always 1/2 * n * (n – 1). As we stated above there are n vertices and each connects to n-1 remaining vertices so the number of edges is the product of n and n-1, but remember that by doing this we count each edge two times once for each vertex which is incident on the edge. So we half the count to get exact number of edges.

The Graph 2 in the above image is a Complete Graph K4.

The Regular Graph

The graph G is a regular graph if all its vertices have the same degree. For e.g. if the degree of a vertex in G is r, then the graph G is said to be regular of degree r.

Few points about the Regular Graph.

  • An example of regular graph is the Null Graph Nn. All such graphs are regular in degree zero.
  • Another example of regular graph is the Complete Graph Kn. All such graphs are regular in degree (n-1).
  • If G has n vertices and it is regular in degree r then G has 1/2 * n * r. Refer the above explanation for number of edges in Complete Graph.

The Bipartite Graph

The graph G is said to be a Bipartite graph if G(V), the vertex set can be divided into two subsets V1 and V2 such that if there exists an edge in the graph, it connects one vertex from each of the sets.

Few points about the Bipartite Graph.

  • A Bipartite Graph can be represented as Km,n where m is the number of vertices in set V1 and n is the number of vertices in set V2.
  • The above point deduces the fact that the total number of vertices in the Bipartite graph is m + n
  • The maximum number of edges in such a graph would be m * n

Below is an image of K3,4. Notice that in a Bipartite Graph, it is not necessary that each vertex from V1 should connect to each vertex in V2. Assume that the blue vertices are in set V1 and the red vertices are in set V2
BIPARTITE

For more on Bipartite Graphs, please refer Wikipedia
The Complete Bipartite Graph

The Bipartite Graph G is said to be a Complete Bipartite Graph each vertex in V1 is connected to each vertex in V2.

Below is an image of K3,4 which is a Complete Bipartite. Assume that the blue vertices are in set V1 and the red vertices are in set V2
COMPLETE BIPARTITE

Note: Similar to Bipartite Graphs there can be Tripartite Graphs as well. That will have three disjoint sets of vertices. May be V1, V2 and V3 and rest all the conditions remain same as Bipartite graphs.

The k-Cubes Graph

This graph belongs to the family of Bipartite Graphs. This graph is represented by Qk and it is such that its vertices correspond to a binary sequences of length k. Which means that the vertices of Q3 will correspond to {000, 001, 010, 011, 100, 101, 110, 111}.
Each of the vertices can be represented by one of the entries in the above set and only those vertices can be connected to each other whose sequence differs just by 1 by one bit.

Few points about the k-Cube Graph.

  • The graph will always be a regular graph of degree k. As each of the vertices will have exactly k vertices to connect to because there are k bit sequences and each bit has a possibility to change. For e.g. in Q3 the vertex corresponding to 000 can connect to vertices corresponding to all these sequences {001, 010, 100}
  • The total number of vertices in the Qk Graph is 2k.
  • The total number of edges in the Qk Graph is 1/2 * k * 2k. We arrived at this calculation because each vertex is of degree k and there are total 2k vertices, so the total number of edges would be the product of degree and number of vertices. But in this calculation we counted each edge for exactly two vertices which are incident on the edge, so we take half of the final numbers.

We can generalize our understanding for Qk.

Below is an image of Q3.
qkgraph

Here is the Bipartite representation of the above Q3 graph.
BRFORKCUBE
We end up this post here with some knowledge of special graphs which are of major importance. In subsequent articles these graphs will be referred many times.

Do not forget to subscribe with your email to receive latest posts on Graph Theory.