KMS Of Academy of mathematics and systems sciences, CAS
| Cycles in 2-connected graphs | |
| Fan, GH; Lv, XZ; Wang, P | |
| 2004-11-01 | |
| 发表期刊 | JOURNAL OF COMBINATORIAL THEORY SERIES B
 |
| ISSN | 0095-8956 |
| 卷号 | 92期号:2页码:379-394 |
| 摘要 | 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. |
| 关键词 | cycles 2-connected graphs extremal graphs |
| DOI | 10.1016/j.jctb.2004.09.003 |
| 语种 | 英语 |
| WOS研究方向 | Mathematics |
| WOS类目 | Mathematics |
| WOS记录号 | WOS:000225169100010 |
| 出版者 | ACADEMIC PRESS INC ELSEVIER SCIENCE |
| 引用统计 | |
| 文献类型 | 期刊论文 |
| 条目标识符 | http://ir.amss.ac.cn/handle/2S8OKBNM/531 |
| 专题 | 中国科学院数学与系统科学研究院 |
| 通讯作者 | Fan, GH |
| 作者单位 | 1.Fuzhou Univ, Ctr Discrete Math, Fujian 350002, Peoples R China 2.Chinese Acad Sci, Inst Syst Sci, Beijing 100080, Peoples R China |
| 推荐引用方式 GB/T 7714 | Fan, GH,Lv, XZ,Wang, P. Cycles in 2-connected graphs[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B,2004,92(2):379-394. |
| APA | Fan, GH,Lv, XZ,&Wang, P.(2004).Cycles in 2-connected graphs.JOURNAL OF COMBINATORIAL THEORY SERIES B,92(2),379-394. |
| MLA | Fan, GH,et al."Cycles in 2-connected graphs".JOURNAL OF COMBINATORIAL THEORY SERIES B 92.2(2004):379-394. |
| 条目包含的文件 | 条目无相关文件。 | |||||
| 个性服务 |
| 推荐该条目 |
| 保存到收藏夹 |
| 查看访问统计 |
| 导出为Endnote文件 |
| 谷歌学术 |
| 谷歌学术中相似的文章 |
| [Fan, GH]的文章 |
| [Lv, XZ]的文章 |
| [Wang, P]的文章 |
| 百度学术 |
| 百度学术中相似的文章 |
| [Fan, GH]的文章 |
| [Lv, XZ]的文章 |
| [Wang, P]的文章 |
| 必应学术 |
| 必应学术中相似的文章 |
| [Fan, GH]的文章 |
| [Lv, XZ]的文章 |
| [Wang, P]的文章 |
| 相关权益政策 |
| 暂无数据 |
| 收藏/分享 |
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。
修改评论