On the strong path partition conjecture

dc.contributor.authorDe Wet, J.P. (Johan)
dc.contributor.authorDunbar, Jean
dc.contributor.authorFrick, Marietjie
dc.contributor.authorOellermann, Ortrud R.
dc.contributor.emailjohan.dewet@up.ac.zaen_US
dc.date.accessioned2023-05-31T12:57:27Z
dc.date.available2023-05-31T12:57:27Z
dc.date.issued2024
dc.description.abstractThe detour order of a graph G, denoted by (G), is the order of a longest path in G. If a and b are positive integers and the vertex set of G can be partitioned into two subsets A and B such that (hAi) ≤ a and (hBi) ≤ b, we say that (A,B) is an (a, b)-partition of G. If equality holds in both instances, we call (A,B) an exact (a, b)-partition. The Path Partition Conjecture (PPC) asserts that if G is any graph and a, b any pair of positive integers such that (G) = a + b, then G has an (a, b)-partition. The Strong PPC asserts that under the same circumstances G has an exact (a, b)-partition. While a substantial body of work in support of the PPC has been developed over the past three decades, no results on the Strong PPC have yet appeared in the literature. In this paper we prove that the Strong PPC holds for a ≤ 8.en_US
dc.description.departmentMathematics and Applied Mathematicsen_US
dc.description.librarianam2023en_US
dc.description.sponsorshipNSERC Discovery Grant CANADA.en_US
dc.description.urihttps://www.dmgt.uz.zgora.plen_US
dc.identifier.citationDe Wet, J.P., Dunbar, J., Frick, M. et al. 2023, 'On the strong path partition conjecture', Discussiones Mathematicae Graph Theory, vol. 44, no. 2, pp. 691-715, doi : 10.7151/dmgt.2468.en_US
dc.identifier.issn1234-3099 (print)
dc.identifier.issn2083-5892 (online)
dc.identifier.other10.7151/dmgt.2468
dc.identifier.urihttp://hdl.handle.net/2263/90992
dc.language.isoenen_US
dc.publisherSciendoen_US
dc.rights© 2022 Johan P. de Wet et al. This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.en_US
dc.subjectStrong path partition conjectureen_US
dc.subjectLongest pathen_US
dc.titleOn the strong path partition conjectureen_US
dc.typeArticleen_US

Files

Original bundle

Now showing 1 - 2 of 2
Loading...
Thumbnail Image
Name:
DeWet_On_2023.pdf
Size:
415.29 KB
Format:
Adobe Portable Document Format
Description:
Online First Article
Loading...
Thumbnail Image
Name:
DeWet_On_2024.pdf
Size:
274.39 KB
Format:
Adobe Portable Document Format
Description:
Article

License bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
license.txt
Size:
1.71 KB
Format:
Item-specific license agreed upon to submission
Description: