Recently, a conjecture due to Hendry was disproved which stated that every Hamiltonian chordal graph is cycle extendible. Here we further explore the conjecture, showing that it fails to hold even when a number of extra conditions are imposed. In particular, we show that Hendry's Conjecture fails for strongly chordal graphs, graphs with high connectivity, and if we relax the definition of "cycle extendible" considerably. We also consider the original conjecture from a subtree intersection model point of view, showing that a result of Abuieda et al is nearly best possible.
翻译:最近,亨德里的推测被推翻,其中指出每个汉密尔顿圆形图都是可循环扩展的。 我们在此进一步探讨这一推测,显示即使在附加一些附加条件的情况下,它也未能保持。 特别是,我们显示亨德里的推测没有达到强烈的圆形图、高度连通性的图,如果我们大大放宽“循环可扩展性”的定义。 我们还从亚树交叉模型的角度来考虑最初的推测,表明阿布伊达等人的结果几乎是最好的。