Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903014 | Discrete Mathematics | 2018 | 9 Pages |
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
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Binlong Li, Hajo Broersma, Shenggui Zhang,