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 (d1 le d2 \leq ... \leq dn). Let D = {i: di = dj 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 di for any i} (missing degrees). It is proved the following location of duplicated degrees:
If di 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{n2/3}2 and \Sigma D+\Sigma M \geq n/2+n2/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