Let $\P$ be any collection of paths of a graph $G=(V,E)$. For $S\subseteq V$, define $I(S)=S\cup\{ v\mid v \ \mbox{ lies in a path of} \ \P \ \mbox{ with endpoints in} \ S\}$. Let $\C$ be the collection of fixed points of the function $I$, that is, $\C=\{ S\subseteq V\mid 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.
Categories: math.CO cs.DM