Characterization of Realization Graphs

Abstract

"Given a degree sequence d, usually it generates several different realizations belonging to several distinct isomorphism classes. In general, the structure of an arbitrary realization cannot be known from its degree sequence, so it may not be possible to determine whether vertices with specified degrees will be adjacent (or non-adjacent), but in some cases it might be possible. The degree sequence is one of the simplest parameters associated with a graph, however, due to the fact that same degree sequence can belong to several pairwise nonisomorphic graphs (different realizations of a given degree sequence) the utility of a degree sequence in a graph problem is limited. Studying the structure of these different realizations of a degree sequence and then, to understand the relationships that exist among graphs with the same degree sequence will be our main focus, which can be very well studied with the help of realization graphs. Graphs constructed by applying some specific rule to any given graph are called auxiliary graphs. Such graphs are often used to translate one graph problem into another. A Realization graph, G(d) is an auxiliary graph defined as the graph (R, d) where R is the set of realizations of d and d is the set of edges where two vertices G, G0 of R are adjacent if and only if performing a single 2-switch can transform G into G0 [3] This thesis consists of several problems related to different realizations of degree sequences. In this thesis, we have looked at various graph families and studied whether they can be characterized by their degree sequences. Also, we have derived some new characteristics for realization graphs. We have also derived a method for verification of whether or not a given degree sequence is uniquely realizable."