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.]
Gk(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 Gk(n,cnk) contains c'n2k 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 G2(n,cn2) contains a subgraph H with c'n2 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 Gk 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 Gk 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 Gk(c,cnk) contains a sub-k-graph Hk with the property that each pair of edges of Hk are contained in a common k-cycle of Hk.
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