A sufficient condition for pancyclability of graphs

doi:10.1016/j.disc.2007.12.063

CSpace

	A sufficient condition for pancyclability of graphs
	Flandrin, E.2; Li, H.2; Wei, B.1,3
	2009-01-06
发表期刊	DISCRETE MATHEMATICS
ISSN	0012-365X
卷号	309 期号:1 页码:144-150
摘要	Let G be a graph of order n and S be a vertex set of q vertices. We call G, S-pancyclable, if for every integer i with 3 <= i <= q there exists a cycle C in G such that \|V (C) boolean AND S\| = i. For any two nonadjacent vertices u, v of S, we say that u, v are of distance two in S, denoted by d(S)(u, v) = 2, if there is a path P in G connecting u and v such that \|V(P) boolean AND S\| <= 3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u, v of S with d(S)(u, v) = 2, max{d(u), d(v)} >= n/2, then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u, v of S with d(S)(u, v) = 2, max{d(u), d(v)} >= n+1/2, then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S = V(G). (C) 2008 Elsevier B.V. All rights reserved.
关键词	Cyclable Induced subgraph S-vertex S-length S-pancyclable
DOI	10.1016/j.disc.2007.12.063
语种	英语
资助项目	NNSF of China ; CNRS of France ; College of Liberal Arts at the University of Mississippi
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000261911400012
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/8767
专题	中国科学院数学与系统科学研究院
通讯作者	Wei, B.
作者单位	1.Univ Mississippi, Dept Math, University, MS 38677 USA 2.Univ Paris 11, LRI, F-91405 Orsay, France 3.Chinese Acad Sci, Acad Math & Syst Sci, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Flandrin, E.,Li, H.,Wei, B.. A sufficient condition for pancyclability of graphs[J]. DISCRETE MATHEMATICS,2009,309(1):144-150.
APA	Flandrin, E.,Li, H.,&Wei, B..(2009).A sufficient condition for pancyclability of graphs.DISCRETE MATHEMATICS,309(1),144-150.
MLA	Flandrin, E.,et al."A sufficient condition for pancyclability of graphs".DISCRETE MATHEMATICS 309.1(2009):144-150.