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
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
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.
Recommended Citation
John, Daniel, "Graph Realizability and Factor Properties Based on Degree Sequence" (2022). Electronic Theses and Dissertations. 8990.
https://scholar.uwindsor.ca/etd/8990