Extremal and Degree Conditions for Path Extendability in Digraphs

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

Research output: Contribution to journalArticleAcademicpeer-review

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

Fingerprint

Degree Condition
Extendability
Digraph
Path
Cycle
Pancyclicity
Hamiltonicity
Tournament
Exception
Contraction
Transform
Imply
Sufficient Conditions

Keywords

  • Path extendability
  • Cycle extendability
  • Digraph
  • Regular tournament

Cite this

Zhang, Zan-Bo ; Zhang, Xiaoyan ; Broersma, Hajo ; Lou, Dingjun. / Extremal and Degree Conditions for Path Extendability in Digraphs. In: SIAM J. Discrete Math. 2017 ; Vol. 31, No. 3. pp. 1990-2014.
@article{4034978d61f34ed4b2b24af5c4789099,
title = "Extremal and Degree Conditions for Path Extendability in Digraphs",
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.",
keywords = "Path extendability, Cycle extendability, Digraph, Regular tournament",
author = "Zan-Bo Zhang and Xiaoyan Zhang and Hajo Broersma and Dingjun Lou",
year = "2017",
doi = "10.1137/16M1077453",
language = "English",
volume = "31",
pages = "1990--2014",
journal = "SIAM journal on discrete mathematics",
issn = "0895-4801",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "3",

}

Extremal and Degree Conditions for Path Extendability in Digraphs. / Zhang, Zan-Bo; Zhang, Xiaoyan; Broersma, Hajo; Lou, Dingjun.

In: SIAM J. Discrete Math., Vol. 31, No. 3, 2017, p. 1990-2014.

Research output: Contribution to journalArticleAcademicpeer-review

TY - JOUR

T1 - Extremal and Degree Conditions for Path Extendability in Digraphs

AU - Zhang, Zan-Bo

AU - Zhang, Xiaoyan

AU - Broersma, Hajo

AU - Lou, Dingjun

PY - 2017

Y1 - 2017

N2 - 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.

AB - 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.

KW - Path extendability

KW - Cycle extendability

KW - Digraph

KW - Regular tournament

U2 - 10.1137/16M1077453

DO - 10.1137/16M1077453

M3 - Article

VL - 31

SP - 1990

EP - 2014

JO - SIAM journal on discrete mathematics

JF - SIAM journal on discrete mathematics

SN - 0895-4801

IS - 3

ER -