##
**Zentralblatt MATH**

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

**Zbl.No: ** 796.05049

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Rousseau, Cecil C.

**Title: ** Extremal problems and generalized degrees. (In English)

**Source: ** Discrete Math. 127, No.1-3, 139-152 (1994).

**Review: ** Authors' abstract: For a positive integer n and a graphical property P, ext_{n}(P) will denote the minimum number of edges in a graph G of order n that satisfies property P, and Ext_{n}(P) will denote the class of graphs with n vertices and ext_{n}(P) edges that have property P. The extremal numbers ext_{n}(P) for properties P that have been commonly used as sufficient conditions for Hamiltonian paths and cycles in graphs will be investigated. In particular, results on the extremal numbers for generalized degree and generalized independent degree properties will be given, where for a fixed positive integer t, the generalized degree \delta_{t}(G) (generalized independent degree \delta^{i}_{t}(G)) is the minimum number of vertices in the union of the neighborhoods of a set of t (independent) vertices of the graph G.

**Reviewer: ** S.Stahl (Lawrence)

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

05C45 Eulerian and Hamiltonian graphs

05C38 Paths and cycles

**Keywords: ** extremal numbers; Hamiltonian paths; cycles; generalized degree; generalized independent degree

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag