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

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
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    Consultation statistics

    This page has been seen 1196 times.
    This article's PDF has been downloaded 779 times.