Conditions for graphs to be path partition optimal

Binlong Li; Hajo Broersma; Shenggui Zhang

doi:10.1016/j.disc.2018.02.011

Conditions for graphs to be path partition optimal

Binlong Li, Hajo Broersma (Corresponding Author), Shenggui Zhang

Research output: Contribution to journal › Article › Academic › peer-review

1 Citation (Scopus)

122 Downloads (Pure)

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.

Original language	English
Pages (from-to)	1350-1358
Number of pages	9
Journal	Discrete mathematics
Volume	341
Issue number	5
DOIs	https://doi.org/10.1016/j.disc.2018.02.011
Publication status	Published - 1 May 2018

Keywords

22/4 OA procedure

Access to Document

10.1016/j.disc.2018.02.011

Li2018conditionsFinal published version, 315 KBLicence: Taverne

Cite this

@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.",

keywords = "22/4 OA procedure",

author = "Binlong Li and Hajo Broersma and Shenggui Zhang",

year = "2018",

month = may,

day = "1",

doi = "10.1016/j.disc.2018.02.011",

language = "English",

volume = "341",

pages = "1350--1358",

journal = "Discrete mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "5",

}

TY - JOUR

T1 - Conditions for graphs to be path partition optimal

AU - Li, Binlong

AU - Broersma, Hajo

AU - Zhang, Shenggui

PY - 2018/5/1

Y1 - 2018/5/1

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.

KW - 22/4 OA procedure

U2 - 10.1016/j.disc.2018.02.011

DO - 10.1016/j.disc.2018.02.011

M3 - Article

SN - 0012-365X

VL - 341

SP - 1350

EP - 1358

JO - Discrete mathematics

JF - Discrete mathematics

IS - 5

ER -

Conditions for graphs to be path partition optimal

Abstract

Keywords

Access to Document

Fingerprint

Cite this