All-path convexity: Combinatorial and complexity aspects

Abstract: Let

P

be any collection of paths of a graph

G = (V, E)

. For

S s u b s e t e q V

, define

I (S) = S c u p v m i d v m b o x l i e s i n a p a t h o f P m b o x w i t h e n d p o i n t s i n S

. Let

C

be the collection of fixed points of the function

I

, that is,

C = S s u b s e t e q V m i d I (S) = S

. It is well known that

(V, C)

is a finite convexity space, where the members of

C

are precisely the convex sets. If

P

is taken as the collection of all the paths of

G

, then

(V, C)

is the {em all-path convexity} with respect to graph

G

. In this work we study how important parameters and problems in graph convexity are solved for the all-path convexity.

This page was built for publication: All-path convexity: Combinatorial and complexity aspects