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