Graph Theory and Various Types of Graphs: A Review

INTRODUCTION

You will find numerous kinds of graphs based on the amount of vertices, selection of edges, interconnectivity, and the general framework of theirs. We will discuss only a certain few important types of graphs in this paper.

A graph having no edges is called a Null Graph. In the above graph, there are three vertices named ‗a‘, ‗b‘, and ‗c‘, but there are no edges among them. Hence it is a Null Graph.

A graph with only one vertex is called a Trivial Graph. In the above shown graph, there is only one vertex ‗a‘ with no other edges. Hence it is a Trivial graph.

A non-directed graph contains edges but the edges are not directed ones. With this graph,' a',' b',' c',' d',' e',' f',' g' are actually the vertices, and' ab',' bc',' cd',' da',' ag',' gf',' ef' are actually the tips of the graph. Because it's a non directed graph, the edges' ab' and' ba' are actually exact same. Similarly various other edges also considered in the exact same way.

In a directed graph, each edge has a direction.

In the above mentioned graph, we've 7 vertices' a',' b',' c',' d',' e',' f', and' g', and 8 edges' ab',' cb',' dc',' ad',' ec',' fe',' gf', and' ga'. As it's a directed graph, each advantage bears an arrow mark which shows the direction of its. Remember that in a directed graph,' ab' is actually different from' ba'.

A graph without any loops as well as no parallel edges is known as a basic graph. The maximum amount of edges possible in a single graph with' n' vertices is actually nC2 exactly where nC2 = n(n - 1)/2. The amount of easy graphs a possibility with' n' vertices = 2nc2 = 2n(n 1)/2. In the next graph, you will find three vertices with three edges that is optimum excluding the parallel edges & loops. This may be proved by utilizing the above mentioned formulae.

A graph G is actually believed to be attached in case there exists a route between every pair of vertices. Generally there must be no less than one advantage for each vertex of the graph. So we are able to claim that it's attached to several other vertex at the other side of the advantage. In the next graph, each vertex has the own edge of its connected to various other advantage. Hence it's a connected graph.

A graph G is actually disconnected, in case it doesn't have a minimum of 2 connected vertices. The following graph is actually a good example of a Disconnected Graph, in which you will find 2 parts, one with' a',' b',' c',' d' vertices and another with' e',' f',' g',' h' vertices. The two components are independent and not connected to each other. Hence it is called disconnected graph. With this example, you will find 2 impartial elements, c-d and a-b-f-e, which aren't connected to one another. Hence this's a disconnected graph.

A graph G is believed to be frequent, in case all its vertices have exactly the same degree. In a graph, if the amount of each vertex is actually' k', then the graph is actually known as a' k regular graph'. In the coming graphs, all of the vertices have exactly the same degree. So these graphs are known as frequent graphs. In both the graphs, all the vertices have degree 2. They are called 2-Regular Graphs.

A hassle-free graph with' n' mutual vertices is actually known as an entire graph and it's denoted by' Kn'. In the graph, a vertex must have tips with any other vertices, then it called a comprehensive graph. Put simply, in case a vertex is attached to any other vertices of a graph, then it's known as a comprehensive graph. In the coming graphs, each vertex in the graph is actually associated with all the remaining vertices of the graph except by itself.

A hassle-free graph with n' vertices (n > = three) as well as n' edges is actually known as a cycle graph in case all the edges of its create a cycle of length n'. In case the amount of each vertex at the graph is 2, then it's known as a Cycle Graph. Notation? Cn Check out the following graphs Graph I has three vertices with three edges that is developing a cycle ab-bc-ca'. Graph II has four vertices with four edges that is developing a cycle pq-qs-sr-rp'. Graph III has five vertices with five edges that is developing a cycle ik-km-ml-lj-ji'. Hence all the given graphs are cycle graphs. by including a brand new vertex. That brand new vertex is actually known as a Hub which is actually linked to each of the vertices of Cn. Notation' Wn No. of edges in Wn = No. of edges from hub to any other vertices No. of edges from any other nodes in cycle graph without having a hub. = (n 1) (n-1) = 2(n 1) Check out the coming graphs. They're all wheel graphs. Inside graph I, it's received from C3 by including an vertex at the center called as' d'. It's denoted as W4. Selection of edges in W4 = 2(n 1) = 2(3) = six In graph II, it's received from C4 by including a vertex at the center called as' t'. It's denoted as W5. Selection of edges in W5 = 2(n 1) = 2(4) = eight In graph III, it's received from C6 by including a vertex at the center called as' o'. It's denoted as W7. Selection of edges in W4 = 2(n 1) = 2(6) = twelve

A graph with at least one cycle is called a cyclic graph. In the above example graph, we have two cycles a-b-c-d-a and c-f-g-e-c. Hence it is called a cyclic graph.

A graph with no cycles is called an acyclic graph.

In the above example graph, we do not have any cycles. Hence it is a non-cyclic graph.

A very simple graph G = (V, E) with vertex partition V = V1, V2 is actually known as a bipartite graph in case every advantage of E joins a vertex inside V1 to a vertex found V2. Generally, a Bipertite graph has 2 sets of vertices, let us say, V2 and V1, and in case an advantage is actually drawn, it should link some vertex in set V1 to any kind of vertex in set V2. In this graph, you can observe two sets of vertices − V1 and V2. Here, two edges named ‗ae‘ and ‗bd‘ are connecting the vertices of two sets V1 and V2.

A bipartite graph' G', G = (V, E) with partition V = V1, V2 is actually believed to become a total bipartite graph in case every vertex inside V1 is actually attached to every vertex of V2. Generally, a comprehensive bipartite graph hooks up each vertex from set V1 to each vertex from set V2. The following graph is actually a comprehensive bipartite graph since it's edges joining each vertex from set V1 to each vertex from set V2. Km,n has (m+n) vertices and (mn) edges. Km,n is a regular graph if m=n. In general, a complete bipartite graph is not a complete graph. Km,n is a complete graph if m=n=1.

A comprehensive bipartite graph of the type K1, n 1 is actually a star graph with n vertices. A star graph is actually a comprehensive bipartite graph in case a single vertex belongs to one set and most of the remaining vertices belong to the various other set. In the above mentioned graphs, out of' n' vertices, all the' n-1' vertices are actually linked to a single vertex. Hence it's in the type of K1, n 1 which are actually star graphs.

A graph in which it's feasible to attain some vertex by traversing the tips from one vertex to the next has been said to be connected. The set of edges used (not always distinct) is actually known as a route between the specified vertices. A graph is believed to be total in case there exists an advantage joining every 2 pairs of vertices. The graph above isn't complete but may be made complete with the addition of additional edges:

1. https://www.geeksforgeeks.org/ mathematics-graph-theory-basics/ 2. https://www.geeksforgeeks.org/ mathematics-graph-theory-basics-set-1/ 3. https://brilliant.org/wiki/graph-theory/ 4. https://medium.com/basecs/a-gentle-introduction-to-graph-theory-77969829ead8 5. https://www.tutorialspoint.com/ graph_theory/types_of_graphs.htm

Assistant Professor in Mathematics, G. B. Degree College Rohtak, Haryana parveshvats555@gmail.com