Show simple item record

dc.contributor.advisorMuthu, Rahul
dc.contributor.authorSoni, Maulik
dc.date.accessioned2020-09-22T06:23:25Z
dc.date.available2023-02-17T06:23:25Z
dc.date.issued2020
dc.identifier.citationSoni, Maulik (2020). Acyclic edge colouring of subgraphs of hypercubes. Dhirubhai Ambani Institute of Information and Communication Technology. ix, 47 p. (Acc.No: T00914)
dc.identifier.urihttp://drsr.daiict.ac.in//handle/123456789/964
dc.description.abstractAcyclic edge colouring is a very important combinatorial optimization problem, which many researchers are currently working on. Acyclic edge colouring is assignment of colours to vertices or edges of the graph such that, no two colour induced subgraph contains any cycle. In its most general form, it is a very difficult problem and thus research work on this problem, usually focuses on some limited aspect. In particular one approach to this problem is to find exact values for the acyclic chromatic index for special families of graphs. One might also look for corresponding efficient algorithms, for such optimal colourings. However, it is essential to study a few papers on this problem of acyclic edge colouring in order to develop one’s techniques and solve a new aspect of this problem. We aim to obtain optimal bounds and algorithms for the acyclic edge colouring problem on the class of subgraphs of hypercubes. We have given the best colour bound of D + 1 (where D is maximum degree of graph), for three categories of subgraphs of hypercubes. First is arbitrary subgraph of any dimensional hypercube, second is (d �� 1)-regular subgraphs of d-dimensional hypercube with constraints of limited 2 and 4 cross edges. and third is 3-regular subgraphs of any dimensional hypercube. We have given the some approaches proven effective from mathematical or simulation point of view. All the colour bounds given by us, are supported by well known, Acyclic Edge Colouring Conjecture. The approach of colouring 3-regular subgraphs of any dimensional hypercube, is not just limited to subgraphs of the hypercube, but it can also be considered for any regular bipartite graph with regularity equals to 3.
dc.publisherDhirubhai Ambani Institute of Information and Communication Technology
dc.subjectEdge colouring
dc.subjectproper edge colouring
dc.subjectacyclic edge colouring
dc.subjecthypercubes
dc.subjectarbitrary subgraphs of hypercubes
dc.subject(d ����� 1)-regular subgraphs of ddimensional hypercubes
dc.subject3-regular subgraphs of hypercubes
dc.titleAcyclic edge colouring of subgraphs of hypercubes
dc.typeDissertation
dc.degreeM. Tech
dc.student.id201811057
dc.accession.numberT00914
dc.accession.number511.1 SON


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record