MSc Thesis Defense Announcement of Daniel John:"Graph realizability and factor properties based on degree sequence"

 

Date: Monday December 19, 2022 

Time:  11:00 AM – 1:00 PM 

Location: Essex Hall, Room 105 

Reminders: Two-part attendance mandatory, arrive 5-10 minutes prior to event starting - LATECOMERS WILL NOT BE ADMITTED once the door has been closed and the presentation has begun. Please be respectful of the presenter by NOT knocking on the door for admittance. 

 

A graph is a structure consisting of a set of vertices and edges. Graph construction has been a focus of research for a long time, and generating graphs has proven helpful in complex networks and artificial intelligence. 

A significant problem that has been a focus of research is whether a given sequence of integers is graphical. Havel and Hakimi stated necessary and sufficient conditions for a degree sequence to be graphic with different properties. In our work, we have proved the sufficiency of the requirements by generating algorithms and providing constructive proof. 

Given a degree sequence, one crucial problem is checking if there is a graph realization with k-factors. For the degree sequence with a realizable k-factor, we analyze an algorithm that produces the realization and its k-factor. We then generate degree sequences having no realizations with connected k-factors. We also state the conditions for a degree sequence to have connected k-factors. 

In our work, we have also studied the necessary and sufficient conditions for a sequence of integer pairs to be realized as directed graphs. We have proved the sufficiency of the conditions by providing algorithms as constructive proofs for the directed graphs 

 

Keywords: Graph realization, k-factor, degree sequence, directed graphs, undirected graphs 

 

Internal Reader:              Dr. Ahmad Biniaz 

External Reader:             Dr. Mehdi Sangani Monfared 

Advisor:                           Dr. Asish Mukhopadhyay 

Chair:                               Dr. Jessica Chen