##
**Zentralblatt MATH**

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

**Zbl.No: ** 515.05048

**Autor: ** Duke, Richard; Erdös, Paul

**Title: ** Subgraphs in which each pair of edges lies in a short common cycle. (In English)

**Source: ** Combinatorics, graph theory and computing, Proc. 13th Southeast. Conf., Boca Raton 1982, Congr. Numerantium 35, 253-260 (1982).

**Review: ** [This article was published in the book announced in Zbl 504.00004.]

G^{k}(n,l) denotes a k-graph having n vertices and l edges. Theorem 1. For each positive constant c and sufficiently large n there exists a positive constant c' such that each G^{k}(n,cn^{k}) contains c'n^{2k} distinct copies of the complete k-partite k-graph having 2 vertices in each colour class. Corollary 1. For each positive constant c there exists a positive constant c' such that for sufficiently large n each G^{2}(n,cn^{2}) contains a subgraph H with c'n^{2} edges which has the property that each pair of edges of H are contained in a cycle of H of length 4 or 6, and each pair of edges which share a common vertex are in a cycle of length 4. An edge E of a k-graph G^{k} is a separating edge if there exists a partition of the vertices into k classes such that E meets each class, but that every other edge of G^{k} meets at most k-1 classes. A k-cycle is a k-graph with at least one edge, having no separating edges, and which is minimal with respect to this property. Corollary 2. For each positive constant c there exists a positive constant c' such that for sufficiently large n each G^{k}(c,cn^{k}) contains a sub-k-graph H^{k} with the property that each pair of edges of H^{k} are contained in a common k-cycle of H^{k}.

**Reviewer: ** W.G.Brown

**Classif.: ** * 05C65 Hypergraphs

05C35 Extremal problems (graph theory)

05C38 Paths and cycles

**Keywords: ** complete k-partite sub-k-graph; girth; separating edge

**Citations: ** Zbl.504.00004

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag