On Chvátal’s Conjecture for the Hamiltonicity of1-Tough Graphs and Their Complements

International Journal of Information Technology

Shin-Shin Kao ; Yuan-Kang Shih ; Hsun Su

关键词: Complement;    degree sum;    Hamiltonian;    tough.;   

DOI  :  10.1999/1307-6892/10009345

学科分类：计算机应用

来源: World Academy of Science, Engineering and Technology (W A S E T)

【 摘 要 】

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.

【 授权许可】

Unknown