论文标题

哈密​​顿的循环可扩展性强烈弦图

Cycle Extendability of Hamiltonian Strongly Chordal Graphs

论文作者

Rong, Guozhen, Li, Wenjun, Wang, Jianxin, Yang, Yongjie

论文摘要

1990年,亨德里(Hendry)猜想所有汉密尔顿弦图都是可扩展的。 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)是否有整数$ k $,以便所有$ k $连接的汉密尔顿弦图都是可扩展的? 后来,提出了比亨德里(Hendry's)强的猜想。在本文中,我们以负面的方式解决所有这些问题。在积极方面,我们添加到周期可扩展图的列表中,另外两个图形类,即哈密顿$ 4 $ - \ textsc {fan} {fan} -free conordal图,其中每个感应的$ k_5- e $都有True Twins,而Hamiltonian $ \ \ \ \ \ \ \ \ \ fextsc {4 \ fextsc {-fandsc {-fandsc {-fandsc {-fandsc {-fandsc {-fandsc {-fextsc)

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$-\textsc{fan}-free chordal graphs where every induced $K_5 - e$ has true twins, and Hamiltonian $\{4\textsc{-fan}, \overline{A} \}$-free chordal graphs.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源