03891408

a

03891408 Duke, Richard Erd\H{o}s, Paul R\"odl, Vojt\v{e}ch More results on subgraphs with many short cycles. Combinatorics, graph theory and computing, Proc. 15th Southeast. Conf., La. State Univ. 1984, Congr. Numerantium 43, 295-300 (1984). 1984 EN cycle Zbl 0547.00011 [For the entire collection see Zbl 0547.00011.] The authors show that for sufficiently large $n$ every graph of order $n$ and size $n^{2-3\epsilon}$ contains a subgraph of order $m$ and size $cn^{2-\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. L.Lesniak