Professional paper

Degree sequence

Snježana Majstorović ; Odjel za matematiku, Sveučilište J. J. Strossmayera u Osijeku, Osijek
Dolores Begović ; studentica Odjel za matematiku, Sveučilište J. J. Strossmayera u Osijeku, Osijek

Abstract

This paper discusses the degree sequence of a finite simple graph. Two well-known criteria which give the necessary and sufficient conditions for a sequence of nonnegative integers to be a degree sequence of a graph have been proved, the Havel-Hakimi theorem and the ErdősGallai theorem. The Havel-Hakimi theorem is based on the residual sequence of the largest element of a degree sequence. Based on the Havel-Hakimi theorem, an algorithm can be developed to determine whether a set of nonnegative integers is a degree sequence. Erdős and Gallai have given a necessary and sufficient condition, which is not of an algorithmic type, for a sequence to be graphic

Keywords

simple graph, degree sequence of a graph, graphical sequence, Havel-Hakimi theorem, degree set

Hrčak ID:

252846

URI

https://hrcak.srce.hr/252846

Publication date:

15.6.2020.

Article data in other languages: croatian

Visits: 1.178 *