MSc Thesis Proposal of Amreeth Rajan Nagarajan:"Generating graphs from degree sequences "

Wednesday, May 5, 2021 - 12:30 to 14:00

SCHOOL OF COMPUTER SCIENCE 

The School of Computer Science is pleased to present… 

MSc Thesis Proposal by: Amreeth Rajan Nagarajan 

 
Date: Wednesday May 5, 2021 
Time: 12:30pm – 2:00pm 
Passcode: If interested in attending this event, contact the Graduate Secretary at csgradinfo@uwindsor.ca
 

Abstract:  

A graph consists of vertices and edges, connecting pairs of vertices. The subject of graph generation has a long history. Initial research focused on creating catalogues of graphs of small size. It has proved useful for creating input instances for different graph algorithms as well as for disproving conjectures or formulating new ones for various graph classes. 
 
A problem that has garnered a lot of attention is that of deciding if a given sequence of n integers d1≥d2≥d3. . . dn is graphical, that is, does there exist a simple graph whose degrees are the di’s. Necessary and sufficient conditions for this have been obtained, among which the most notable ones are those of Erdos & Gallai and Havel & Hakimi. In our work, we have studied the problem of constructing a forest of trees from such a degree sequence as well split graphs (a split graph is a chordal graph whose complement is also chordal). 
 
Given a degree sequence, there can be many graphs that satisfy it. An important problem is to be able to sample uniformly at random sample from the space of all possible graphs that satisfy a given degree sequence. This has been extensively studied by researchers in the area of complex networks (for example social, neural, metabolic, protein-protein interaction networks). In our work we have studied both the sampling problem as well as the enumeration problem. 
Keywords: Graph generation, Sampling Problem, Forests, Split graphs, Complex networks 
 

MSc Thesis Committee: 

Internal Reader: Dr. Dan Wu
External Reader: Dr. Yash Aneja
Advisor: Dr. Asish Mukhopadhyay
 

MSc Thesis Proposal Announcement

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