Кафедра математики

Permanent URI for this collection

Now showing 1 - 2 of 2

All-path convexity: two characterizations, general position number, and one algorithm
(2024) Haponenko, Vladyslav; Kozerenko, Sergiy
We present two characterizations for the all-path convex sets in graphs. Using the first criterion, we obtain a new characterization of connected block graphs and compute the general position number in a graph with respect to the all-path convexity. The second criterion allows us to provide a new algorithm for testing a set on all-path convexity.
S4 separation and p-partition in all-path and detour convexities
(2026) Haponenko, Vladyslav
In this work, we consider problems of S4 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 S2, S3, and S4 separable graphs are characterized. Also, we present necessary and sufficient conditions for two sets to be S4 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 S4 separable with respect to all-path convexity.