Structural properties of realization graphs

Abstract

All 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.