Distribution of cycle lengths in graphs

doi:10.1006/jctb.2001.2071

CSpace

	Distribution of cycle lengths in graphs
	Fan, GH
	2002-03-01
发表期刊	JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN	0095-8956
卷号	84 期号:2 页码:187-202
摘要	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
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000174627100001
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/17008
专题	中国科学院数学与系统科学研究院
通讯作者	Fan, GH
作者单位	Chinese Acad Sci, Inst Syst Sci, Beijing 10080, Peoples R China
推荐引用方式 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.