All-path convexity: Combinatorial and complexity aspects

Abstract

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} \ ¶\ \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.

11 pages