Please use this identifier to cite or link to this item: http://drsr.daiict.ac.in//handle/123456789/988
Full metadata record
DC FieldValueLanguage
dc.contributor.advisorMuthu, Rahul
dc.contributor.authorSapara, Dhara
dc.date.accessioned2020-09-22T17:33:03Z
dc.date.available2023-02-17T17:33:03Z
dc.date.issued2020
dc.identifier.citationSapara, Dhara (2020). Structural properties of realization graphs. Dhirubhai Ambani Institute of Information and Communication Technology. vi, 50 p. (Acc.No: T00903)
dc.identifier.urihttp://drsr.daiict.ac.in//handle/123456789/988
dc.description.abstractAll graphs considered in this thesis are simple undirected graphs with finite, nonempty vertex sets. Degree sequence is one of the simplest terms associated with a graph. However, most graph families are not degree determined. This of course means that, the degree sequence of a graph can have more than one realization. Clearly, therefore, these realizations can belong to different isomorphism classes. A 2-switch is an operation by which we can get all possible realizations of a degree sequence. We have studied papers that address necessary and sufficient conditions on a 2-switch, as a result of which the isomorphism class of a graph gets changed. Listing down all possible realizations using 2-switches is a central problem of our thesis. Studying the relation between realizations is our primary focus, which can be done with the help of the realization graph G(d). In this thesis, we have obtained several structural properties of realization graphs. We have also considered the overlap of realization graphs (both labeled and unlabeled versions) with various class of graphs including the class of graphs with long induced cycles. We obtained the following results pertaining to labeled G(d): listing all possible graph structures (degree sequences can be inferred) having a unique realization graph, structures which give complete graph as a G(d), configurations yielding arbitrary sized induced star structure in realization graph, and large cliques in realization graph. We have carried out an exhaustive analysis of the realization graphs of k-regular graphs. We have considered the closely related problem of generating graphs with a specified numbers of induced P4, C4, and 2K2.This is relevant because these configurations constitute the exhaustive list of induced structures whose presence enables a possible 2-switch.
dc.subjectRealization Graph
dc.subjectDegree Sequence
dc.subjectUnigraph
dc.subjectAlternating 4-cycle
dc.subject2-switch
dc.classification.ddc510 SAP
dc.titleStructural properties of realization graphs
dc.typeDissertation
dc.degreeM. Tech
dc.student.id201811083
dc.accession.numberT00903
Appears in Collections:M Tech Dissertations

Files in This Item:
File Description SizeFormat 
201811083.pdf
  Restricted Access
453.67 kBAdobe PDFView/Open Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.