### Abstract

Original language | English |
---|---|

Pages (from-to) | 1350-1358 |

Number of pages | 9 |

Journal | Discrete mathematics |

Volume | 341 |

Issue number | 5 |

DOIs | |

Publication status | Published - 1 May 2018 |

### Fingerprint

### Cite this

*Discrete mathematics*,

*341*(5), 1350-1358. https://doi.org/10.1016/j.disc.2018.02.011

}

*Discrete mathematics*, vol. 341, no. 5, pp. 1350-1358. https://doi.org/10.1016/j.disc.2018.02.011

**Conditions for graphs to be path partition optimal.** / Li, Binlong; Broersma, Hajo (Corresponding Author); Zhang, Shenggui.

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

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.

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

JF - Discrete mathematics

SN - 0012-365X

IS - 5

ER -