All-path convexity: Combinatorial and complexity aspects
share
Let be any collection of paths of a graph G=(V,E). For S⊆ V, define I(S)=S∪{v| v S}. Let be the collection of fixed points of the function I, that is, ={S⊆ V| I(S)=S}. It is well known that (V,) is a finite convexity space, where the members of are precisely the convex sets. If is taken as the collection of all the paths of G, then (V,) is the 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.
READ FULL TEXT