Long cycles in triangle-free graphs with prescribed independence number and connectivity

doi:10.1016/j.jctb.2003.05.002

CSpace

	Long cycles in triangle-free graphs with prescribed independence number and connectivity
	Enomoto, H ; Kaneko, A ; Saito, A ; Wei, B
	2004-05-01
发表期刊	JOURNAL OF COMBINATORIAL THEORY SERIES B
ISSN	0095-8956
卷号	91 期号:1 页码:43-55
摘要	The Chvatal-Erdos theorem says that a 2-connected graph with alpha(G) less than or equal to kappa(G) is hamiltonian. We extend this theorem for triangle-free graphs. We prove that if G is a 2-connected triangle-free graph of order n with alpha(G) less than or equal to 2kappa(G) - 2, then every longest cycle in G is dominating, and G has a cycle of length at least min{n - alpha(G) + kappa(G), n}. (C) 2003 Elsevier Inc. All rights reserved.
关键词	longest cycle triangle-free graph independence number connectivity
DOI	10.1016/j.jctb.2003.05.002
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics
WOS记录号	WOS:000221001900003
出版者	ACADEMIC PRESS INC ELSEVIER SCIENCE
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/1006
专题	中国科学院数学与系统科学研究院
通讯作者	Enomoto, H
作者单位	1.Keio Univ, Dept Math, Kohoku Ku, Yokohama, Kanagawa 2238522, Japan 2.Kogakuin Univ, Dept Elect Engn, Shinjuku Ku, Tokyo 1638677, Japan 3.Nihon Univ, Dept Math Appl, Setagaya Ku, Tokyo 1568550, Japan 4.Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Enomoto, H,Kaneko, A,Saito, A,et al. Long cycles in triangle-free graphs with prescribed independence number and connectivity[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B,2004,91(1):43-55.
APA	Enomoto, H,Kaneko, A,Saito, A,&Wei, B.(2004).Long cycles in triangle-free graphs with prescribed independence number and connectivity.JOURNAL OF COMBINATORIAL THEORY SERIES B,91(1),43-55.
MLA	Enomoto, H,et al."Long cycles in triangle-free graphs with prescribed independence number and connectivity".JOURNAL OF COMBINATORIAL THEORY SERIES B 91.1(2004):43-55.