 |
Discrete Mathematics & Theoretical Computer Science |
Manuel Lafond ; Ben Seamone ; Rezvan Sherkati - Further results on Hendry's Conjecture
dmtcs:6700 - Discrete Mathematics & Theoretical Computer Science, August 22, 2022, vol. 24, no 2 - https://doi.org/10.46298/dmtcs.6700 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.
Comment: 9 pages, 2 figures. The results in this manuscript were originally presented at the Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM) in 2015. v2: Edited to acknowledge recent similar results obtained by Rong at al (arXiv:2007.04698 [cs.DM])
- Source : OpenAIRE Graph
- Funder: Natural Sciences and Engineering Research Council of Canada