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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page