Extremal and degree donditions 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 journal on discrete mathematics
Volume31
Issue number3
DOIs
Publication statusPublished - 2017

Keywords

  • Path extendability
  • Cycle extendability
  • Digraph
  • Regular tournament
  • 22/4 OA procedure

Fingerprint

Dive into the research topics of 'Extremal and degree donditions for path extendability in digraphs'. Together they form a unique fingerprint.

Cite this