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 dn2 edges contains a subgraph with d2n2(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