• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
成果搜索

author:

Fan, GH (Fan, GH.) [1] (Scholars:范更华) | Lv, XZ (Lv, XZ.) [2] | Wang, P (Wang, P.) [3]

Indexed by:

Scopus SCIE

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:

2-connected graphs cycles extremal graphs

Community:

  • [ 1 ] Fuzhou Univ, Ctr Discrete Math, Fujian 350002, Peoples R China
  • [ 2 ] Chinese Acad Sci, Inst Syst Sci, Beijing 100080, Peoples R China

Reprint 's Address:

  • 范更华

    [Fan, GH]Fuzhou Univ, Ctr Discrete Math, Fujian 350002, Peoples R China

Show more details

Version:

Related Keywords:

Related Article:

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

Online/Total:392/10789776
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1