MSc Thesis Proposal Announcement by Daniel John:"Graph realizability and factor properties based on degree sequences"

 

Date: Friday September 16th, 2022 

Time: 10:00am-11:00am 

Passcode: If interested in attending this event, contact the Graduate Secretary at csgradinfo@uwindsor.ca with sufficient notice before the event to obtain the passcode.

 

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 d1, d2,…, dn is graphical. Havel and Hakimi have stated necessary and sufficient conditions for a degree sequence to be graphic with different properties such as multigraphs without loops, connected, connected non-separable, and connected separable graphs. In our work, we have proved the sufficiency of the requirements by generating algorithms and providing constructive proof. 

 

For a degree sequence, there might exist a realization with k-factors, and the k-factors of a graph can be connected and non-connected. This thesis explores determining if a degree sequence has at least one realization with a connected k-factor and identifying the sequences without any realization of the graph with connected k-factors. We also discuss the methods to generate graphic sequences which can realize graphs with connected k-factors. 

 

Keywords: Graphical degree sequence, k-factor, graph generation 

 

Internal Reader:              Dr. Ahmad Biniaz 

External Reader:             Dr. Mehdi Sangani Monfared 

Advisor:                           Dr. Asish Mukhopadhyay