Conditions for graphs to be path partition optimal

Binlong Li, Hajo Broersma, Shenggui Zhang

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

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 languageEnglish
Pages (from-to)1350-1358
Number of pages9
JournalDiscrete Mathematics
Volume341
Issue number5
DOIs
StatePublished - May 2018

Keywords

  • Forbidden subgraph
  • Heavy subgraph
  • Heft index
  • Path partition number
  • Path partition optimal
  • Separable degree

Fingerprint

Dive into the research topics of 'Conditions for graphs to be path partition optimal'. Together they form a unique fingerprint.

Cite this