Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 714.05033
Autor: Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title: Subgraphs of minimal degree k. (In English)
Source: Discrete Math. 85, No.1, 53-58 (1990).
Review: For k \geq 2, any graph G with n vertices and (k-1)(n-k+2)+\binom{k- 2}{2} edges has a subgraph of minimum degree at least k; however, this subgraph need not be proper. It is shown that if G has at least (k-1)(n- k+2)+\binom{k-2}{2}+1 edges, then there is a subgraph H of minimal degree k that has at most n-\sqrt{n}/\sqrt{6k3} vertices. Also, conditions that insurethe existence of smaller subgraphs of minimum degree k are given.
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: subgraph of minimum degree
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag