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, extn(P) will denote the minimum number of edges in a graph G of order n that satisfies property P, and Extn(P) will denote the class of graphs with n vertices and extn(P) edges that have property P. The extremal numbers extn(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 \deltat(G) (generalized independent degree \deltait(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