Indexed by:
Abstract:
Let Gn be a class of graphs on n vertices. For an integer c, let ex (Gn, c) be the smallest integer such that if G is a graph in Gn with more than ex (Gn, c) edges, then G contains a cycle of length more than c. A classical result of Erdös and Gallai is that if Gn is the class of all simple graphs on n vertices, then ex (Gn, c) = c/2 (n-1). The result is best possible when n-1 is divisible by c-1, in view of the graph consisting of copies of Kc all having exactly one vertex in common. Woodall improved the result by giving best possible bounds for the remaining cases when n-1 is not divisible by c-1, and conjectured that if Gn is the class of all 2-connected simple graphs on n vertices, then ex(Gn, c) = max {f(n, 2, c), f(n, ⌊c/2⌋, c)}, where f(n,t,c) = (c+1-t 2) + t(n-c-1+t), 2 ≤t≤c/2, is the number of edges in the graph obtained from Kc+1-t by adding n-(c+1-t) isolated vertices each joined to the same t vertices of Kc+1-t. By using a result of Woodall together with an edge-switching technique, we confirm Woodall's conjecture in this paper. © 2004 Elsevier Inc. All rights reserved.
Keyword:
Reprint 's Address:
Email:
Source :
Journal of Combinatorial Theory. Series B
ISSN: 0095-8956
Year: 2004
Issue: 2 SPEC. ISS.
Volume: 92
Page: 379-394
0 . 6 1 8
JCR@2004
1 . 2 0 0
JCR@2023
JCR Journal Grade:1
Cited Count:
SCOPUS Cited Count: 12
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 2
Affiliated Colleges: