• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    Tensor Product and Acyclic Edge Colouring

    Thumbnail
    View/Open
    201511018 (599.3Kb)
    Date
    2017
    Author
    Shihora, Rutvi
    Metadata
    Show full item record
    Abstract
    "The assignment of colours to the edges of graph G such that no two adjacent edges get the same colour and there is no 2-coloured cycle in G is known as Acyclic Edge Colouring. The minimum number of colours needed to acyclically edge colour the graph is known as acyclic chromatic index and is denoted by a0(G). The difference between a0(G) and 4(G) is known as the gap of the graph. Determining the value of a0(G) either algorithmically or theoretically has been a very difficult problem. It belongs to the class of NP-complete problems. The value of a0(G) has not yet been determined even for the highly structured class of graphs like complete graphs.Determining the exact values of a0(G) even for very special classes of graphs is still open. Tensor Product, also known as Kronecker Product is a special type of graph product. Any graph that can be represented as a tensor product has the same number of irreducible factors, even though the factor graphs may be different for different factorizations. There exists an algorithm that recognizes tensor product graphs in polynomial time and finds a factorization for the same. This thesis addresses the problem of finding a0(G) for a graph G which is a tensor product of either K2, paths or cycles. We have provided optimal and sub-optimal colouring techniques for colouring the tensor product graph, whose factors are either gap 0 or gap 1 graphs. This thesis focuses on the tensor product graphs whose factors are specific gap 0 and gap 1 graphs which are edges, paths or cycles. This can later be extended to arbitrary gap 0 and gap 1 graphs."
    URI
    http://drsr.daiict.ac.in//handle/123456789/698
    Collections
    • M Tech Dissertations [820]

    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     


    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV