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

dc.accession.numberT00720
dc.classification.ddc004.022 SHE
dc.contributor.advisorMuthu, Rahul
dc.contributor.authorSheth, Heli
dc.date.accessioned2019-03-19T09:30:55Z
dc.date.accessioned2025-06-28T10:22:25Z
dc.date.available2019-03-19T09:30:55Z
dc.date.issued2018
dc.degreeM. Tech
dc.description.abstractThis 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.
dc.identifier.citationSheth, Heli (2018). Total Graphs Properties of Total Graphs and Dynamic Construction of Total Graphs. Dhirubhai Ambani Institute of Information and Communication Technology, vi, 39 p. (Acc. No: T00720)
dc.identifier.urihttp://drsr.daiict.ac.in/handle/123456789/754
dc.publisherDhirubhai Ambani Institute of Information and Communication Technology
dc.student.id201611033
dc.subjectAuxiliary graph
dc.subjectAlgorithms
dc.titleTotal graphs properties of total graphs and dynamic construction of total graphs
dc.typeDissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
201611033_Heli Sheth.pdf
Size:
2.33 MB
Format:
Adobe Portable Document Format
Description:
201611033