Indexed by:
Abstract:
Let G(n) 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 G(n) with more than ex(G(n), c) edges, then G contains a cycle of length more than c. A classical result of Erdos and Gallai is that if G(n) is the class of all simple graphs on n vertices, then ex (G(n), c)(2)(/c) = (n - 1). The result is best possible when n - 1 is divisible by c - 1, in view of the graph consisting of copies of K-c 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 G(n), is the class of all 2-connected simple graphs on n vertices, then ex (G(n), 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 less than or equal to t less than or equal to 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. (C) 2004 Elsevier Inc. All rights reserved.
Keyword:
Reprint 's Address:
Version:
Source :
JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN: 0095-8956
Year: 2004
Issue: 2
Volume: 92
Page: 379-394
0 . 6 1 8
JCR@2004
1 . 2 0 0
JCR@2023
ESI Discipline: MATHEMATICS;
JCR Journal Grade:1
Cited Count:
WoS CC Cited Count: 13
SCOPUS Cited Count: 12
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: