Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 840.05033
Autor: Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.
Title: Edge conditions for the existence of minimal degree subgraphs. (In English)
Source: Alavi, Yousef (ed.) et al., Graph theory, combinatorics, and applications, Vol. 1. Proceedings of the sixth quadrennial international conference on the theory and applications of graphs held at Western Michigan University, Kalamazoo, Michigan, May 30-June 3, 1988. New York: John Wiley & Sons Ltd. Wiley-Interscience Publication. 419-434 (1991).
Review: For m > n and k positive integers, f(m, n, k) denotes the smallest positive integer such that any graph of order m and size f(m, n, k) has a subgraph of order n and minimum degree at least k. The function f(m, n, k) is investigated: upper and lower bounds are given for f, and exact values are determined for f when m- n is small and k = 2. Also, for the special case k = 2, sharper bounds for f(m, n, k) are proved. Extremal graphs are described when exact results are obtained. Similar results are given for the related function g(m, n, k), which is the smallest positive integer such that any graph of order m, size g(m, n, k), and minimum degree at least k has a subgraph of order n and minimum degree at least k.
Classif.: * 05C35 Extremal problems (graph theory)
Keywords: extremal graphs; subgraph; minimum degree; bounds
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag