##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 772.05052

**Autor: ** Duke, Richard; Erdös, Paul; Rödl, Vojtech

**Title: ** Extremal problems for cycle-connected graphs. (In English)

**Source: ** Combinatorics, graph theory, and computing, Proc. 22nd Southeast Conf., Baton Rouge/LA (USA) 1991, Congr. Numerantium 83, 147-151 (1991).

**Review: ** [For the entire collection see Zbl 747.00034.]

Let *H* be a fixed collection of graphs. A graph G is *H*-connected if, for every pair of edges of G, there is a subgraph H of G that contains both edges and lies in *H*. In this and several earlier papers, the authors have focussed attention on the case when *H* consists of a small number of even-length cycles. The goal in this work has been to bound the number of edges in a graph that will ensure that it contains a large *H*-connected subgraph. Having previously given best-possible such bounds in the cases when *H* consists of all even cycles of length at most six and when *H* consists of all even cycles of length at most twelve, the authors consider here the case when *H* consists of all even cycles of length at most eight. Their main result is that, for a positive constant d, an n-vertex graph with dn^{2} edges contains a subgraph with d^{2}n^{2}(1-o(1)) edges in which every pair of edges lie on a cycle of length 4, 6, or 8.

**Reviewer: ** J.G.Oxley (Baton Rouge)

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C40 Connectivity

**Keywords: ** cycle-connected graph; Erdös-Ko-Rado theorem

**Citations: ** Zbl 747.00034

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag