Extremal and Degree Conditions for Path Extendability in Digraphs

Zan-Bo Zhang, Xiaoyan Zhang, Hajo Broersma, Dingjun Lou

    Research output: Contribution to journalArticleAcademicpeer-review

    1 Citation (Scopus)

    Abstract

    In the study of cycles and paths, the meta-conjecture of Bondy that sufficient conditions for Hamiltonicity often imply pancyclicity has motivated research on the existence of cycles and paths of many lengths. Hendry further introduced the stronger concepts of cycle extendability and path extendability, which require that every cycle or path can be extended to another one with one additional vertex. These concepts have been studied extensively, but there exist few results on path extendability in digraphs, as far as we know. In this paper, we make the first attempt in this direction. We establish a number of extremal and degree conditions for path extendability in general digraphs. Moreover, we prove that every path of length at least two in a regular tournament is extendable, with some exceptions. One of our proof approaches is a new contraction operation to transform nonextendable paths into nonextendable cycles.
    Original languageEnglish
    Pages (from-to)1990-2014
    Number of pages25
    JournalSIAM J. Discrete Math.
    Volume31
    Issue number3
    DOIs
    Publication statusPublished - 2017

    Keywords

    • Path extendability
    • Cycle extendability
    • Digraph
    • Regular tournament

    Fingerprint Dive into the research topics of 'Extremal and Degree Conditions for Path Extendability in Digraphs'. Together they form a unique fingerprint.

  • Cite this