##
**Zentralblatt MATH**

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

**Zbl.No: ** 776.05057

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

**Title: ** Cycle-connected graphs. (In English)

**Source: ** Discrete Math. 108, No.1-3, 261-278 (1992).

**Review: ** A graph G is called K-connected, K a fixed collection of graphs, if every pair of edges of G is contained in a subgraph S of G, where S in K. The authors discuss C_{4}-connected graphs, where C_{4} is a cycle of length four and compute the constant c'' such that there exists a graph with cn^{2} edges (n = |V(G)|) in which the largest C_{4}-connected subgraph has size at most c''.

**Reviewer: ** M.Hager (Leonberg)

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

05C38 Paths and cycles

05C40 Connectivity

**Keywords: ** cycle-connected graphs; multipartite graphs

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag