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

author:

Fan, G. (Fan, G..) [1] | Lv, X. (Lv, X..) [2] | Wang, P. (Wang, P..) [3]

Indexed by:

Scopus

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:

2-connected graphs; Cycles; Extremal graphs

Community:

  • [ 1 ] [Fan, G.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian 350002, China
  • [ 2 ] [Lv, X.]Institute of Systems Science, Chinese Academy of Sciences, Beijing 100080, China
  • [ 3 ] [Wang, P.]Institute of Systems Science, Chinese Academy of Sciences, Beijing 100080, China

Reprint 's Address:

  • [Fan, G.]Center for Discrete Mathematics, Fuzhou University, Fuzhou, Fujian 350002, China

Show more details

Related Keywords:

Related Article:

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:

WoS CC 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:

Online/Total:365/10792970
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