Skip to the main content

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


Full text: croatian pdf 445 Kb

page 39-52

downloads: 190

cite


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

Article data in other languages: croatian

Visits: 416 *