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

Monday, December 19, 2022 - 11:00 to 13:00


The School of Computer Science is pleased to present… 

MSc Thesis Defense by: Daniel John 

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 

MSc Thesis Committee:  

Internal Reader:              Dr. Ahmad Biniaz 
External Reader:             Dr. Mehdi Sangani Monfared 
Advisor:                           Dr. Asish Mukhopadhyay 
Chair:                               Dr. Jessica Chen 

MSc Thesis Defense Announcement 


5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716