Total graphs properties of total graphs and dynamic construction of total graphs

Abstract

This thesis involves studying total graphs which are auxiliary graphs used to transform the total colouring problem of a graph into vertex colouring problem of the total graph. Not all graphs are total graphs but each graph has a unique total graph. Work has been done on recognizing total graphs. So one of the important problems in total graphs is to convert any given non-total graph into total graph by using minimum number of operations on graphs i.e. dynamic construction of total graphs. The main goal of this research was to devise dynamic algorithms which give the largest sub-graph of the given graph which is total. To start with, we have tried to analyse the parameters like clique number, radius, diameter, etc. of total graphs in terms of the original graph and have obtained many results. Also, we discovered another interesting problem in total graphs which is finding the intersection of graph classes with total graphs. This thesis includes results on realizing many special classes of graphs as total graphs. Also, a better algorithmic approach for finding the largest sub-graph of the given input graph has been suggested. However, the suggested algorithm guarantees to give locally optimal solution but does not guarantee a globally optimal solution. The implementation of the previous algorithm and the algorithm that we have suggested has been done and output analysis has been carried out on a range of inputs.