首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Tough graphs and hamiltonian circuits
Authors:V Chvátal
Institution:Centre de Recherches Mathématiques, Université de Montréal, Montréal, Canada
Abstract:The toughness of a graph G is defined as the largest real number t such that deletion of any s points from G results in a graph which is either connected or else has at most s/t components. Clearly, every hamiltonian graph is 1-tough. Conversely, we conjecture that for some t0, every t0-tough graph is hamiltonian. Since a square of a k-connected graph is always k-tough, a proof of this conjecture with t0 = 2 would imply Fleischner's theorem (the square of a block is hamiltonian). We construct an infinite family of (32)-tough nonhamiltonian graphs.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号