Cycle Extendability of Hamiltonian Strongly Chordal Graphs
Cycle Extendability of Hamiltonian Strongly Chordal Graphs
复制标题
哈密尔顿强弦图的循环可延性
DOI：
10.1137/20m1369920
复制
发表时间：
2020-07
影响因子：
0.8
通讯作者：
Yongjie Yang
中科院分区：
文献类型：
--
作者：
Guozhen Rong;Wenjun Li;Jianxin Wang;Yongjie Yang
1990年，Hendry猜想所有的哈密尔顿弦图都是圈可扩的。在一系列论文证实了这一猜想之后，拉丰和西蒙在2015年驳斥了这一猜想。考虑到它们的反例不是强弦图，而且它们都只是$2$-连通的，Lafond和Seamone提出了以下两个问题：(1)哈密尔顿强弦图是圈可扩的吗？(2)是否存在一个整数$k$使得所有$k$-连通的哈密尔顿弦图都是圈可扩的？后来，提出了一个比亨德利的猜想更有力的猜想。在本文中，我们从否定的角度解决了这些问题。在积极的方面，我们在圈可扩展图的列表中增加了另外两个图类，即哈密尔顿$4$-叶幂和哈密顿{4-扇，$-OVERLINE{A}$}-自由弦图。
In 1990, Hendry conjectured that all Hamiltonian chordal graphs are cycle extendable. After a series of papers confirming the conjecture for a number of graph classes, the conjecture is yet refuted by Lafond and Seamone in 2015. Given that their counterexamples are not strongly chordal graphs and they are all only $2$-connected, Lafond and Seamone asked the following two questions: (1) Are Hamiltonian strongly chordal graphs cycle extendable? (2) Is there an integer $k$ such that all $k$-connected Hamiltonian chordal graphs are cycle extendable? Later, a conjecture stronger than Hendry's is proposed. In this paper, we resolve all these questions in the negative. On the positive side, we add to the list of cycle extendable graphs two more graph classes, namely, Hamiltonian $4$-leaf powers and Hamiltonian {4-FAN, $\overline{A}$}-free chordal graphs.
登录
查看更多内容
DOI：
10.1016/j.disc.2006.03.030
发表时间：
2006-07
期刊：
Discret. Math.
影响因子：
--
作者：
D. Rautenbach
通讯作者：
D. Rautenbach
影响因子：
0.7
作者：
Ragnar Nevries;Christian Rosenke
通讯作者：
Ragnar Nevries;Christian Rosenke
DOI：
--
发表时间：
2017
期刊：
--
影响因子：
--
作者：
Aydın Gerek
通讯作者：
Aydın Gerek
DOI：
10.2307/3616070
发表时间：
1973-12
期刊：
The Mathematical Gazette
影响因子：
--
作者：
K. Fraughnaugh
通讯作者：
K. Fraughnaugh
DOI：
10.1007/978-3-8348-9329-1_2
发表时间：
2010
期刊：
--
影响因子：
--
作者：
M. Loebl
通讯作者：
M. Loebl