Splittable and Highly Connectable Degree Sequences

Abstract

This work explores the broad domain of the relationship between graphs withthe same degree sequence, aiming to find a degree sequence characterization forcertain graph classes. Degree sequences represent the sequence of degrees of verticesin a graph. While degree sequences alone do not guarantee the structure ofa graph, they can provide a foundation for further development and offer conditionsthat can be tested in linear time.Earlier work in this domain includes graph classes that are degree determined,meaning that their membership can be determined solely based on the degreesequence. Examples of such classes include complete graphs, split graphs, andthreshold graphs. Linear time algorithms exist for recognizing whether a degreesequence belongs to these classes. The concept of 2-switch operations was introduced,which involve edge deletion and addition to change the adjacencies in agraph. Performing a 2-switch operation may change the isomorphism class of thegraph. The configurations in a 2-switch operation that lead to a change in theisomorphism class have been studied. Realization graphs are used to study therelationship between different realizations of a degree sequence. It was shownthat realization graphs are always connected, as a consequence of the Fulkerson,Hoffman, and McAndrew theorem.In this thesis Our contribution to this domain involves solving two specific problems.These are : study of disconnected realizations and highly connected realizationsof degree sequences. The definitions and notation used throughout the workare presented, including the definitions of degree sequence, graphic sequence, unigraphicdegree sequence, and the Havel-Hakimi construction method.The abstract provides an overview of the study�s focus on degree sequences, graphclasses, 2-switch operations, realization graphs, and their properties.