Application of (0, 1)-Matrix in Determination of Graphic Realization of Non-Increasing Positive Integer Sequence
Prantik Biswas, Abhisek Paul, Paritosh Bhattacharya · 2015
A finite sequence of nonnegative integers is said to be graphical if there exists a finite simple graph, such that the degrees of its vertices corresponds to the terms of the sequence. Such a graph is often termed as a realization of the given degree sequence. In this paper we have proposed an algorithm that determines the realization of a given degree sequence by constructing the adjacency matrix from the given sequence. The input to the algorithm is a non-increasing sequence of positive integers. The output of the algorithm is the decision (graphic or non-graphic), along with the adjacency matrix, provided the sequence is graphical.