24.1.8. Special Types of Undirected Graphs

Now let us define some special types of undirected graphs. So, the first special type of undirected graph is a complete graph. And the property of this graph is that you have exactly one edge between each pair of distinct vertices. And since this is a simple graph and our property is that you cannot have more than one edge between every pair of distinct vertices. Automatically we have here the restriction that you cannot have a self-loop, because if you have a self-loop then that self-loop will be violating the definition here. So, the requirement here is that you take the vertices, all the vertices between every pair of distinct vertices you will have exactly one edge. You do not have the option of 0 or 1, exactly 1 edge should be there between every pair of distinct vertices and if n is the number of nodes in a complete graph then we use this notation K to denote a complete graph with n nodes.

A complete graph is a type of graph where every possible pair of distinct vertices is connected by a single edge. This means that for a set of n vertices, every vertex can connect to every other vertex exactly once, resulting in the maximum number of edges possible without any repetitions. In a complete graph, there are no self-loops, which means a vertex cannot connect to itself. This creates a highly interconnected structure. For instance, if there are 4 vertices in a complete graph, there will be 6 edges because each vertex connects to 3 others, and thus, the total number of edges is calculated as n*(n-1)/2.

Imagine a group of friends at a party where each person shakes hands with every other person exactly once. If there are 4 friends, they will have a total of 6 handshakes (edges) as each shakes hands with the others. This is similar to a complete graph where every vertex (friend) is connected (has an edge) to every other vertex.

Then another special type of simple and directed graph is a cycle graph denoted as C . Here the vertex set will be consisting of n nodes and you will have { (v1, v2), (v2, v3),…,(vn-1, vn), (vn, v1) }. Now since the graph is simple, the cycle graph is defined only when the number of vertices is n ≥ 3.

A cycle graph is a specific type of graph that forms a closed loop. It consists of vertices connected in such a way that if you start from one vertex and follow the edges, you will return to the starting point after visiting all the vertices exactly once. This structure requires at least 3 vertices (n ≥ 3) to form a loop; with only 2 vertices, you would not be able to create a cycle without repeating an edge. Thus, cycle graphs demonstrate the concept of connectivity and circular paths in graph theory.

Think of a race track in the shape of a circle. Cars (vertices) start at one point, drive around the track, and return to the same starting point without leaving the track. This circular path represents a cycle graph.

Then there is another special simple and directed graph called as the wheel graph. It is slightly different from the cycle graph, so what you do is you take a cycle graph involving n - 1 nodes and then you add a central vertex which is the nth vertex and the central vertex is now we add an edge involving this central vertex and all the vertices in your cycle graph C.

A wheel graph is built by adding a central vertex to an existing cycle graph. The cycle graph consists of n-1 vertices arranged in a circular way. The central vertex is connected to all the vertices of the cycle, creating a structure that resembles a wheel, where the cycle forms the rim and the center forms the hub. This structure enhances connectivity as each node in the cycle is directly connected to the center.

Consider a bicycle wheel: the tire represents the cycle (the outer vertices) while the hub in the center represents the central vertex. Each spoke (the edges) connects the hub to the tire, symbolizing the edges of the wheel graph.

We also have another special simple undirected graph called as the n cube or the hyper cube denoted by this notation Q . So, this graph will have 2n nodes, where each node represents a possible n bit string. So, remember that the number of bit strings of length n is 2n, so each string is represented by a node in this hypercube graph and you have an edge between the ith vertex and the jth vertex if the bit strings represented by the ith vertex and the jth vertex differ in exactly one bit position.

The hypercube graph is a multi-dimensional graph that organizes vertices based on binary strings of a fixed length n. Each vertex corresponds to a unique binary string, and an edge exists between two vertices if their binary strings differ by exactly one bit. For example, in a 2-dimensional hypercube (Q2), there are 4 vertices (00, 01, 10, 11), with edges connecting those that differ by a single digit. This structure allows for efficient representation and traversal within high-dimensional spaces.

Imagine a light switch panel with n switches. Each switch can either be 'on' (1) or 'off' (0). The hypercube graph represents all possible configurations of the switches. If you toggle a single switch, that creates a direct connection (edge) to a new configuration. This is how the hypercube graphs visually and structurally represent connections between different states.

Now let us next define what we call as Bipartite graphs. So, if you are given a simple graph, then the graph is called bipartite, if we can find out two vertex sets V1 and V2 such that the following whole the vertex sets V1 and V2 should constitute a partition of your vertex set.

A bipartite graph is characterized by its ability to split its vertices into two distinct sets, where each edge connects vertices from one set to another but never within the same set. This means that you cannot have edges connecting vertices from the same set. This structure is useful in various applications, such as matching problems or scheduling, where relationships exist between two distinct groups.

Think of a classroom where a teacher (one set) assigns homework to students (the other set). Each assignment is an edge connecting a teacher and a student, but there are no 'student-to-student' assignments. This illustrates how bipartite graphs function: two different groups interacting based on specific relations.

So, that brings me to the end of this lecture these are the references used for today's lecture. So, the basic concepts related to graph theory you can find in the Rosen book, but there is also this advanced or dedicated book for graph theory.

A complete bipartite graph is a special case of bipartite graphs where every vertex from the first set is connected to every vertex in the second set. This means that there are no 'missing' edges between the two sets, creating a fully connected structure. For instance, if one set has 3 vertices and the other has 4, there will be a total of 12 edges connecting them, demonstrating maximum connectivity between the two disjoint sets.

Think of a situation where every employee (first set) must give a presentation to every client (second set). Each employee presents to each client directly, leaving no connections out. This represents a complete bipartite graph, where each element in one set is paired with every element in the other.

--