Toughness and hamiltonicity in k-trees
Toughness and hamiltonicity in k-trees
复制标题
k 树中的韧性和哈密顿性
DOI：
10.1016/j.disc.2005.11.051
复制
发表时间：
2007-04
影响因子：
0.8
通讯作者：
Broersma, Hajo
中科院分区：
文献类型：
--
作者：
Yoshimoto, Kiyoshi;Xiong, Liming;Broersma, Hajo
我们考虑韧性条件，保证存在的一个哈密尔顿圈在k-树，弦图类的一个子类。根据Chen等人的结果，18-坚韧弦图是哈密尔顿图，根据Bauer等人的结果，存在韧性任意接近74的不可迹弦图。一般认为，保证弦图哈密尔顿性的韧性的最佳可能值小于18，但Chen等人的证明表明，证明一个更好的结果可能非常复杂。我们证明了至少三个顶点上的每一个1-坚韧2-树都是哈密尔顿的，这是一个最好的可能结果，因为1-坚韧性是哈密尔顿性的必要条件。我们把这个结果推广到k-树，其中k ≠ 2：设G是k-树。若G的韧性至少为（k+1）/3，则G是Hamilton的。此外，我们提出了无限类的非哈密顿1-坚韧的k-树，每个k <$3。
We consider toughness conditions that guarantee the existence of a hamiltonian cycle in k-trees, a subclass of the class of chordal graphs. By a result of Chen et al. 18-tough chordal graphs are hamiltonian, and by a result of Bauer et al. there exist nontraceable chordal graphs with toughness arbitrarily close to 74. It is believed that the best possible value of the toughness guaranteeing hamiltonicity of chordal graphs is less than 18, but the proof of Chen et al. indicates that proving a better result could be very complicated. We show that every 1-tough 2-tree on at least three vertices is hamiltonian, a best possible result since 1-toughness is a necessary condition for hamiltonicity. We generalize the result to k-trees for k⩾2: Let G be a k-tree. If G has toughness at least (k+1)/3, then G is hamiltonian. Moreover, we present infinite classes of nonhamiltonian 1-tough k-trees for each k⩾3.
登录
查看更多内容
DOI：
10.1016/s0166-218x(99)00141-9
发表时间：
2000-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
D. Bauer;H. Broersma;H. J. Veldman
通讯作者：
D. Bauer;H. Broersma;H. J. Veldman
DOI：
10.1016/s0166-218x(99)00142-0
发表时间：
2000-02
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
D. Bauer;G. Katona;D. Kratsch;H. J. Veldman
通讯作者：
D. Bauer;G. Katona;D. Kratsch;H. J. Veldman
影响因子：
0.5
作者：
KEIL, JM
通讯作者：
KEIL, JM
DOI：
10.1002/(sici)1097-0118(199912)32:4
发表时间：
1999-12
期刊：
J. Graph Theory
影响因子：
--
作者：
T. Böhme;B. Mohar;M. Stiebitz
通讯作者：
T. Böhme;B. Mohar;M. Stiebitz
影响因子：
2.1
作者：
Guantao Chen;M. Jacobson;André E. Kézdy;J. Lehel
通讯作者：
Guantao Chen;M. Jacobson;André E. Kézdy;J. Lehel