The Study of Cycles in 2-connected Graphs Specifically Odd Graphs

dc.accession.numberT00686
dc.classification.ddc006.31 THA
dc.contributor.advisorMuthu, Rahul
dc.contributor.authorThakker, Avani
dc.date.accessioned2019-03-19T09:30:50Z
dc.date.accessioned2025-06-28T10:19:17Z
dc.date.available2019-03-19T09:30:50Z
dc.date.issued2018
dc.degreeM. Tech
dc.description.abstractCounting the number of cycles in an undirected graph is a classical problemwhich is known to be intractable and so research on this problem typically focuses on approximation algorithms, special cases, heuristics and some variants of the problem. This problem has been extensively studied for its applications in areas of communication systems, artificial intelligence and signal processing. In Complexity theory, this problem lies in the class of #P-complete problem. There may be exponentially many simple cycles in a graph. We observed growth in the number of cycles by adding ears to a 2-connected graph. As analyzed, the growth was exponential. Counting or finding cycles and paths of graphs like complete graphs, presents no interest, in particular since everything is already known analytically. Hence, we studied the cycle structure in Odd Graphs. We analytically obtained cycle lengths that are certainly present in an odd graph without traversing the graph structure. Further, we added minimal number of edges to an odd graph to make the graph pancyclic.
dc.identifier.citationThakker, Avani (2018). The Study of Cycles in 2-connected Graphs Specifically Odd Graphs. Dhirubhai Ambani Institute of Information and Communication Technology, vi, 22 p. (Acc. No: T00686)
dc.identifier.urihttp://drsr.daiict.ac.in/handle/123456789/730
dc.publisherDhirubhai Ambani Institute of Information and Communication Technology
dc.student.id201611025
dc.subjectGraph
dc.subjectAlgorithms
dc.subjectArtificial Intelligence
dc.subjectSignal Processing
dc.subjectHeuristics
dc.subjectPancyclic
dc.titleThe Study of Cycles in 2-connected Graphs Specifically Odd Graphs
dc.typeDissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
201611025_Avani_Thakker.pdf
Size:
537.54 KB
Format:
Adobe Portable Document Format
Description:
201611025