Hamiltonicity in 3-domination-critical graphs with alpha=delta+2

CSpace

	Hamiltonicity in 3-domination-critical graphs with alpha=delta+2
	Tian, F; Wei, B; Zhang, L
	1999-03-15
发表期刊	DISCRETE APPLIED MATHEMATICS
ISSN	0166-218X
卷号	92 期号:1 页码:57-70
摘要	Let delta, gamma, and alpha be respectively the minimum degree, the domination number and the independence number of a graph G. The graph G is 3-gamma-critical if gamma=3 and the addition of any edge decreases gamma by 1. It was conjectured that any connected 3-gamma-critical graph with delta greater than or equal to 2 is hamiltonian. In Fararon et al. (J. Graph Theory, 25 (1997) 173-184.) it was proved alpha less than or equal to delta + 2; and moreover, if alpha less than or equal to delta + 1, then G is hamiltonian. Here we show that if alpha=delta + 2 then G is hamiltonian, and thus prove the conjecture. We also give a class of 3-gamma-critical graphs with alpha=delta + 2. (C) 1999 Elsevier Science B.V. All rights reserved.
关键词	domination-critical graphs Hamiltonicity longest cycle
语种	英语
WOS研究方向	Mathematics
WOS类目	Mathematics, Applied
WOS记录号	WOS:000079426100003
出版者	ELSEVIER SCIENCE BV
引用统计
文献类型	期刊论文
条目标识符	http://ir.amss.ac.cn/handle/2S8OKBNM/14487
专题	中国科学院数学与系统科学研究院
通讯作者	Tian, F
作者单位	Acad Sinica, Inst Syst Sci, Beijing 100080, Peoples R China
推荐引用方式 GB/T 7714	Tian, F,Wei, B,Zhang, L. Hamiltonicity in 3-domination-critical graphs with alpha=delta+2[J]. DISCRETE APPLIED MATHEMATICS,1999,92(1):57-70.
APA	Tian, F,Wei, B,&Zhang, L.(1999).Hamiltonicity in 3-domination-critical graphs with alpha=delta+2.DISCRETE APPLIED MATHEMATICS,92(1),57-70.
MLA	Tian, F,et al."Hamiltonicity in 3-domination-critical graphs with alpha=delta+2".DISCRETE APPLIED MATHEMATICS 92.1(1999):57-70.