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 -
Further results on Hendry's Conjecture

Authors: Manuel Lafond ; Ben Seamone ; Rezvan Sherkati

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.

Volume: vol. 24, no 2
Section: Graph Theory
Published on: August 22, 2022
Accepted on: July 13, 2022
Submitted on: August 6, 2020
Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics


Consultation statistics

This page has been seen 51 times.
This article's PDF has been downloaded 43 times.