##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 685.05025

**Autor: ** Burr, Stefan A.; Erdös, Paul; Faudree, Ralph J.; Gyárfás, A.; Schelp, R.H.

**Title: ** Extremal problems for degree sequences. (In English)

**Source: ** Combinatorics, Proc. 7th Hung. Colloq., Eger/Hung. 1987, Colloq. Math. Soc. János Bolyai 52, 183-193 (1988).

**Review: ** [For the entire collection see Zbl 673.00009.]

Let G be a graph of order n with degree sequence (d_{1} le d_{2} \leq ... \leq d_{n}). Let D = **{**i: d_{i} = d_{j} for some i\ne j**}** (duplicated degrees) and S = **{**1,...,n**}**-D (single degrees). Let D' be that proper subset of D which one obtains in choosing the first index associated with each duplicated degree. Finally let M = **{**j: 0 \leq j \leq n-1 and j\ne d_{i} for any i**}** (missing degrees). It is proved the following location of duplicated degrees:

If d_{i} in S for all i > k, then k \geq (\sqrt{4(n-\delta)+1}+1)/2 where elta = 0 for n even, and \delta = 1 for n odd, and this result is best possible. Let \Sigma D and \Sigma D' be the sum of the degrees indexed by each of the sets. There are given bounds for these numbers, e.g.: If G has no isolated vertices, then \Sigma D' \geq 1 and \Sigma D \geq \frac{n+3}{3} and these bounds are sharp. Furthermore let \Sigma M be the sum of the elements in M. For sufficiently large n one has \Sigma D'+\Sigma M \geq \frac{n^{2/3}}2 and \Sigma D+\Sigma M \geq n/2+n^{2/3}/2 and these bounds are sharp in order of magnitude.

**Reviewer: ** K.Engel

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** irregularity; duplicated degree; missing degree; extremal problem; degree sequence

**Citations: ** Zbl 673.00009

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag