Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  559.05038
Autor:  Duke, Richard; Erdös, Paul; Rödl, Vojtech
Title:  More results on subgraphs with many short cycles. (In English)
Source:  Combinatorics, graph theory and computing, Proc. 15th Southeast. Conf., La. State Univ. 1984, Congr. Numerantium 43, 295-300 (1984).
Review:  [For the entire collection see Zbl 547.00011.]
The authors show that for sufficiently large n every graph of order n and size n2-3\epsilon contains a subgraph of order m and size cn2-\epsilon, where c does not depend on m, n or \epsilon, in which every two edges are on a cycle of length at most 6, and that apart from the value of c this result is best possible, i.e., 3 cannot be replaced by any smaller value.
Reviewer:  L.Lesniak
Classif.:  * 05C38 Paths and cycles
Keywords:  cycle
Citations:  Zbl 547.00011

© 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