Date of Award

Fall 2021

Publication Type

Thesis

Degree Name

M.A.Sc.

Department

Computer Science

Keywords

Complex networks, Forests, Graph generation, Sampling problem, Split graphs

Supervisor

Y. Aneja

Supervisor

D. Wu

Rights

info:eu-repo/semantics/openAccess

Creative Commons License

Creative Commons Attribution 4.0 International License
This work is licensed under a Creative Commons Attribution 4.0 International License.

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 extended 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 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. We have improved upon previously established enumeration methods and have turned them into sampling methods. The different methods have been compared and their complexities have been analyzed.

Download

Share

COinS