Skoči na glavni sadržaj

Osječki matematički list, Vol. 20 No. 1, 2020.

Stručni rad

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

Puni tekst: hrvatski pdf 445 Kb

str. 39-52

preuzimanja: 749

citiraj

Sažetak

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

Ključne riječi

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

Hrčak ID:

252846

URI

https://hrcak.srce.hr/252846

Datum izdavanja:

15.6.2020.

Podaci na drugim jezicima: hrvatski

Posjeta: 1.814 *