$S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES

Vladyslav Haponenko

$S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES

Abstract

In this work, we consider problems of $S_{4}$ and $p$-convex partition separations with respect to the all-path and the detour convexities. We give characterizations of $p$-all-path convex and $p$-detour convex graphs. With respect to all-path convexity $S_{2}$, $S_{3}$, and $S_{4}$ separable graphs are characterized. Also, we present necessary and sufficient conditions for two sets to be $S_{4}$ separable, for both convexities. Moreover, we prove that in all-path convexity the time complexity of those problems is linear, and it is NP-hard for detour convexity. Finally, we give an algorithm for determining whether two sets in graph are $S_{4}$ separable with respect to all-path convexity.

Keywords

Thanks

I want to thank the Ukrainian military for keeping Mena safe. I also express my gratitude to my scientific supervisor, Sergiy Kozerenko, without whom this paper would not be possible. Finally, I would like to thank the anonymous referees for their valuable comments and suggestions, which helped improve the quality of this work.

References

[1] Nielsen, M. H. and Oellermann, O. R., (2012), Separation properties of 3-Steiner and 3-monophonic convexity in graphs, Discrete Mathematics, 312(22), pp. 3293-3305.
[2] Elaroussi, M., Nourine, L. and Vilmin, S., (2024), Half-space separation in monophonic convexity, arXiv preprint arXiv:2404.17564.
[3] Farber, M. and Jamison, R. E., (1986), Convexity in graphs and hypergraphs, SIAM Journal on Algebraic Discrete Methods, 7(3), pp. 433-444.
[4] Chartrand, G., Johns, G. L. and Tian, S., (1993), Detour distance in graphs, In Annals of discrete mathematics, 55, pp. 127-136.
[5] Santhakumaran, A. P. and Chandran, S. U., (2018), The detour hull number of a graph, Algebra and discrete mathematics, 14(2), pp. 307-322.
[6] Arco, R. and Canoy Jr, S., (2017), Detour convexity in graphs, Journal of Analysis and Applications, 15(2), pp. 117-131.
[7] Seiffarth, F., Horvath, T. and Wrobel, S., (2023), Maximal closed set and half-space separations in finite closure systems, Theoretical Computer Science, 973, p. 114105.
[8] Gonzalez, L. M., Grippo, L. N., Safe, M. D. and dos Santos, V. F., (2020), Covering graphs with convex sets and partitioning graphs into convex sets, Information Processing Letters, 158, p. 105944.

Details

Primary Language

English

Subjects

Combinatorics and Discrete Mathematics (Excl. Physical Combinatorics)

Journal Section

Research Article

Authors

Vladyslav Haponenko ^* This is me
0009-0001-1064-2512
Ukraine

Publication Date

April 7, 2026

Submission Date

March 6, 2025

Acceptance Date

July 30, 2025

Published in Issue

Year 2026 Volume: 16 Number: 4

IZ

https://izlik.org/JA66CP59RL

Cite

RIS / Bibtex

APA

Haponenko, V. (2026). $S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES. TWMS Journal of Applied and Engineering Mathematics, 16(4), 443-456. https://izlik.org/JA66CP59RL

AMA

1.Haponenko V. $S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES. JAEM. 2026;16(4):443-456. https://izlik.org/JA66CP59RL

Chicago

Haponenko, Vladyslav. 2026. “$S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES”. TWMS Journal of Applied and Engineering Mathematics 16 (4): 443-56. https://izlik.org/JA66CP59RL.

EndNote

Haponenko V (April 1, 2026) $S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES. TWMS Journal of Applied and Engineering Mathematics 16 4 443–456.

IEEE

[1]V. Haponenko, “$S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES”, JAEM, vol. 16, no. 4, pp. 443–456, Apr. 2026, [Online]. Available: https://izlik.org/JA66CP59RL

ISNAD

Haponenko, Vladyslav. “$S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES”. TWMS Journal of Applied and Engineering Mathematics 16/4 (April 1, 2026): 443-456. https://izlik.org/JA66CP59RL.

JAMA

1.Haponenko V. $S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES. JAEM. 2026;16:443–456.

MLA

Haponenko, Vladyslav. “$S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES”. TWMS Journal of Applied and Engineering Mathematics, vol. 16, no. 4, Apr. 2026, pp. 443-56, https://izlik.org/JA66CP59RL.

Vancouver

1.Vladyslav Haponenko. $S_{4}$ SEPARATION AND P-PARTITION IN ALL-PATH AND DETOUR CONVEXITIES. JAEM [Internet]. 2026 Apr. 1;16(4):443-56. Available from: https://izlik.org/JA66CP59RL