KMS Of Academy of mathematics and systems sciences, CAS
Distribution of cycle lengths in graphs | |
Fan, GH | |
2002-03-01 | |
Source Publication | JOURNAL OF COMBINATORIAL THEORY SERIES B |
ISSN | 0095-8956 |
Volume | 84Issue:2Pages:187-202 |
Abstract | Bondy and Vince proved that every graph with minimum degree at least three contains two cycles whose lengths differ by one or two, which answers a question raised by Erdos. By a different approach. we show in this paper that if G is a graph with minimum degree delta(G) greater than or equal to 3k for any positive integer k, then G contains k + 1 cycles C-0, C-1,..., C-k such that k+ 1 < \E(C-0)\ < \E(C-1)\ <... < \E(C-k)\, \E(C-1)\ - \E(Cl - 1)\ = 2. i less than or equal to i less than or equal to k - 1. and 1 less than or equal to \E(C-k)\ - \E(Ck-1)\ less than or equal to 2, and further-more, if delta(G) greater than or equal to 3(k+1), then \E(C-k)\ - \E(Ck-1)\ = 2, To settle a problem proposed by Bondy and Vince, we obtain that if G is a nonbipartite 3-connected graph with minimum degree at least 3k for any positive integer k. then G contains 2k cycles of consecutive lengths m, m+ 1, ..., m +2k - 1 for some integer m greater than or equal to k+2. (C) 2001 Elsevier Science (USA). |
DOI | 10.1006/jctb.2001.2071 |
Language | 英语 |
WOS Research Area | Mathematics |
WOS Subject | Mathematics |
WOS ID | WOS:000174627100001 |
Publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE |
Citation statistics | |
Document Type | 期刊论文 |
Identifier | http://ir.amss.ac.cn/handle/2S8OKBNM/17008 |
Collection | 中国科学院数学与系统科学研究院 |
Corresponding Author | Fan, GH |
Affiliation | Chinese Acad Sci, Inst Syst Sci, Beijing 10080, Peoples R China |
Recommended Citation GB/T 7714 | Fan, GH. Distribution of cycle lengths in graphs[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B,2002,84(2):187-202. |
APA | Fan, GH.(2002).Distribution of cycle lengths in graphs.JOURNAL OF COMBINATORIAL THEORY SERIES B,84(2),187-202. |
MLA | Fan, GH."Distribution of cycle lengths in graphs".JOURNAL OF COMBINATORIAL THEORY SERIES B 84.2(2002):187-202. |
Files in This Item: | ||||||
There are no files associated with this item. |
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
Edit Comment