### Abstract

Language | English |
---|---|

Pages | 1350-1358 |

Number of pages | 9 |

Journal | Discrete mathematics |

Volume | 341 |

Issue number | 5 |

DOIs | |

State | Published - 2018 |

### Fingerprint

### Cite this

*Discrete mathematics*,

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

}

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

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

Research output: Contribution to journal › Article

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 -