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

Year 2026, Volume: 16 Issue: 4 , 443 - 456 , 07.04.2026

Vladyslav Haponenko

https://izlik.org/JA66CP59RL

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

all-path convexity , graph convexity , detour convexity , convex separation , $p$-partition

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.
• [9] Haponenko, V. and Kozerenko, S., (2024), All-Path Convexity: Two Characterizations, General Position Number, and One Algorithm, Discrete Math. Lett., 13, pp. 58–65.
• [10] van De Vel, M. L., (1993), Theory of convex structures, Elsevier, 50.
• [11] Tarjan, R., (1972), Depth-first search and linear graph algorithms, SIAM journal on computing, 1(2), pp. 146-160.
• [12] Centeno, C. C., Dantas, S., Dourado, M. C., Rautenbach, D. and Szwarcfiter, J. L., (2010), Convex partitions of graphs induced by paths of order three, Discrete Mathematics & Theoretical Computer Science, 12(5), pp. 175-184.