Skoči na glavni sadržaj

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: 190

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

Podaci na drugim jezicima: hrvatski

Posjeta: 416 *