WASET
	%0 Journal Article
	%A Shin-Shin Kao and  Yuan-Kang Shih and  Hsun Su
	%D 2018
	%J International Journal of Mathematical and Computational Sciences
	%B World Academy of Science, Engineering and Technology
	%I Open Science Index 133, 2018
	%T On Chvátal’s Conjecture for the Hamiltonicity of  1-Tough Graphs and Their Complements
	%U https://publications.waset.org/pdf/10009345
	%V 133
	%X In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.

	%P 20 - 23