Conditions for graphs to be path partition optimal

Binlong Li, Hajo Broersma, Shenggui Zhang

Research output: Contribution to journalArticle

Abstract

The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.
LanguageEnglish
Pages1350-1358
Number of pages9
JournalDiscrete mathematics
Volume341
Issue number5
DOIs
StatePublished - 2018

Fingerprint

Optimal Partition
Hamiltonians
Path
Partition
Graph in graph theory
Optimality
Degree Condition
Hamiltonian Graph
Hamiltonicity
Induced Subgraph
Connected graph

Cite this

Li, Binlong ; Broersma, Hajo ; Zhang, Shenggui. / Conditions for graphs to be path partition optimal. In: Discrete mathematics. 2018 ; Vol. 341, No. 5. pp. 1350-1358
@article{f2c3145444ee4390850bda7fa0850e25,
title = "Conditions for graphs to be path partition optimal",
abstract = "The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.",
author = "Binlong Li and Hajo Broersma and Shenggui Zhang",
year = "2018",
doi = "10.1016/j.disc.2018.02.011",
language = "English",
volume = "341",
pages = "1350--1358",
journal = "Discrete mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "5",

}

Conditions for graphs to be path partition optimal. / Li, Binlong; Broersma, Hajo; Zhang, Shenggui.

In: Discrete mathematics, Vol. 341, No. 5, 2018, p. 1350-1358.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Conditions for graphs to be path partition optimal

AU - Li,Binlong

AU - Broersma,Hajo

AU - Zhang,Shenggui

PY - 2018

Y1 - 2018

N2 - The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.

AB - The path partition number of a graph is the minimum number of edges we have to add to turn it into a Hamiltonian graph, and the separable degree is the minimum number of edges we have to add to turn it into a 2-connected graph. A graph is called path partition optimal if its path partition number is equal to its separable degree. We study conditions that guarantee path partition optimality. We extend several known results on Hamiltonicity to path partition optimality, in particular results involving degree conditions and induced subgraph conditions.

U2 - 10.1016/j.disc.2018.02.011

DO - 10.1016/j.disc.2018.02.011

M3 - Article

VL - 341

SP - 1350

EP - 1358

JO - Discrete mathematics

T2 - Discrete mathematics

JF - Discrete mathematics

SN - 0012-365X

IS - 5

ER -