Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  767.05056
Autor:  Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.
Title:  Extremal problems involving vertices and edges on odd cycles. (In English)
Source:  Discrete Math. 101, No.1-3, 23-31 (1992).
Review:  Let G be a graph on n vertices and with \lfloor n2/4\rfloor+1 or more edges. The authors investigate the minimum of the number of vertices and edges of G which are on triangles and, more generally, cycles of length 2k+1. They also conjecture that if k \geq 2 then at least 2n2/9-O(n) edges of G are on cycles of length 2k+1.
Reviewer:  J.Sedlácek (Praha)
Classif.:  * 05C35 Extremal problems (graph theory)
05C38 Paths and cycles
Keywords:  extremal problems; odd cycles; Turán graph

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag