Theses and Dissertations

Permanent URI for this collectionhttp://ir.daiict.ac.in/handle/123456789/1

Browse

Filters

Settings

Has files: YesSubject: search.filters.subject.Auxiliary graph

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    ItemOpen Access
    Total graphs properties of total graphs and dynamic construction of total graphs
    (Dhirubhai Ambani Institute of Information and Communication Technology, 2018) Sheth, Heli; Muthu, Rahul
    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.
  • Thumbnail Image
    ItemOpen Access
    Set labeling of graphs
    (Dhirubhai Ambani Institute of Information and Communication Technology, 2018) Kumar, Lokesh; Muthu, Rahul
    Given a universal set and its subsets, intersection graph can be characterized as the graph with one distinct subset of given universal set for each vertex of the graph and any two non-adjacent vertices have no element common in their respective set. This was first studied by Erdos. For Kneser graph and Petersen graph, adjacency is characterized by disjointness. This motivates us to look at disjointness instead of intersection. This report contains results about asymptotic bounds for valid labeling of some special classes of graphs such as harary graphs, split graphs, bipartite graphs, disjoint complete graphs and complete multipartite graphs. Parameters relevant to study of labeling of vertices of the graphs are minimum label size possible (ILN), minimum universe size possible (USN) and their uniform versions such as UILN and UUSN. We have also proposed one framework to label disconnected graphs.