Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 840.05050
Autor: Erdös, Paul; Faudree, Ralph J.; Gyárfás, A.; Schelp, R.H.
Title: Odd cycles in graphs of given minimum degree. (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. 407-418 (1991).
Review: The principal result of the paper is that any nonbipartite 2-connected graph on n vertices of minimum degree \geq 2n/(k+2) (k a fixed odd integer and n large) contains a k-cycle or is isomorphic to the following graph H. The graph H has n vertices (with n divisible by k+2) and is obtained from the (k+2)-cycle by replacing each of its k+2 vertices by an independent set of order n/(k+2).
Classif.: * 05C38 Paths and cycles
05C35 Extremal problems (graph theory)
Keywords: cycle; minimum degree; independent set
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag