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.
翻译：全路径凸性：组合学和复杂性方面
翻译后的摘要：
令$\P$为图$G=(V,E)$的任何路径集合。对于$S\subseteq V$，定义$I(S)=S\cup\{v\mid v$在$\P$中具有端点在$S$中的路径中$\}$。令$\C$是函数$I$的不动点集合，即$\C=\{S\subseteq V\mid I(S)=S\}$。众所周知，$(V,\C)$是一个有限的凸空间，其中$\C$的成员正是凸集合。如果将$\P$取为$G$的所有路径的集合，则$(V,\C)$是图$G$的全路径凸性。在本文中，我们研究了在全路径凸性下，图凸性中的重要参数和问题如何得到解决。
相关内容
微信扫码咨询专知VIP会员