Monday, December 19, 2022 - 11:00 to 13:00
SCHOOL OF COMPUTER SCIENCE
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 firstname.lastname@example.org