"Graph Realizability and Factor Properties Based on Degree Sequence" by Daniel John

Date of Award

2022

Publication Type

Thesis

Degree Name

M.Sc.

Department

Computer Science

Keywords

Degree sequence, Directed graphs, Graphs, k-factors, Undirected graphs

Supervisor

A. Mukhopadhyay

Supervisor

A. Biniaz

Rights

info:eu-repo/semantics/openAccess

Abstract

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.

Share

COinS