论文标题
关键集，皇冠和本地最大独立套件
Critical sets, crowns, and local maximum independent sets
论文作者
论文摘要
如果$ s $没有两个顶点，则设置$ s \ subseteq v（g）$是独立的（或稳定），而通过$ \ mathrm {indrm {indrm {indrm {g）$，我们的意思是所有独立集合$ g $的集合。 如果$ \ left \ welet \ vert a \ right \ vert \ vert n（a）\ wert n（a） n（i）\ right \ vert：i \ in \ mathrm {ind}（g）\} $，其中$ n（i）$表示$ i $的附近。 如果$ s \ in \ mathrm {ind}（g）$，并且从$ n（s）$到$ s $的匹配，则$ s $是一个皇冠，我们在crown（g）$中编写$ s \。 令$ψ（g）$为所有局部最大独立集的$ g $的家族，即，如果$ s $是$ s \ cup cup n（s）$引起的子图中的最大独立集，则$ s \inψ（g）$。 在本文中，我们表明$ critindep（g）\ subseteq crown（g）$ $ \subseteqψ（g）$对于每个图都是正确的。此外，我们还提供了一些类别的图表，其中这些家族重合和形成贪婪的贪婪，甚至是我们称为增强素的更通用的集合系统。
A set $S\subseteq V(G)$ is independent (or stable) if no two vertices from $S$ are adjacent, and by $\mathrm{Ind}(G)$ we mean the set of all independent sets of $G$. A set $A\in\mathrm{Ind}(G)$ is critical (and we write $A\in CritIndep(G)$) if $\left\vert A\right\vert -\left\vert N(A)\right\vert =\max\{\left\vert I\right\vert -\left\vert N(I)\right\vert :I\in \mathrm{Ind}(G)\}$, where $N(I)$ denotes the neighborhood of $I$. If $S\in\mathrm{Ind}(G)$ and there is a matching from $N(S)$ into $S$, then $S$ is a crown, and we write $S\in Crown(G)$. Let $Ψ(G)$ be the family of all local maximum independent sets of graph $G$, i.e., $S\inΨ(G)$ if $S$ is a maximum independent set in the subgraph induced by $S\cup N(S)$. In this paper we show that $CritIndep(G)\subseteq Crown(G)$ $\subseteqΨ(G)$ are true for every graph. In addition, we present some classes of graphs where these families coincide and form greedoids or even more general set systems that we call augmentoids.
