ABSTRACT

A graph involves a pictorial representation of objects and their relations. Algebraically, it is represented in a minimum way as an ordered pair of two sets viz., set of vertices, representing objects and the set of edges, representing the relations. If we remove some vertices from the existing graph, the resulting subgraph is denoted as an induced subgraph. If we randomly remove some edges, the resultant subgraph need not be an induced subgraph. Hence, a subgraph need not be an induced subgraph but all induced subgraphs are subgraphs. Induced subgraphs are studied extensively in the area of structural studies of graphs and networks. Retaining all the vertices of a graph but removing all the edges and then joining all the pairs of vertices that are not adjacent by edges generates the complement of a graph. The anti-Gallai graph of a graph has the edges of the graph as its vertices.