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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page