The family of all local maximum independent sets is an augmentoid

Abstract

It was proved in (Levit and Mandrescu, 2022) that both $(V(G),Crown(G))$ and $(V(G),CritIndep(G))$ are augmentoids, established partial augmentation phenomena for the family $\Psi (G)$ of local maximum independent sets, and asked in Problem~5.5 to characterize the graphs whose family $\Psi (G)$ is an augmentoid. We prove that the answer is positive in full generality: for every finite simple graph $G$, the set system $(V(G),\Psi (G))$ is an augmentoid. The proof is constructive. If $S,T\in \Psi (G)$, then the explicit choice \[ A=S \setminus N[T],\qquad B=T \setminus N[S] \] satisfies \[ T\cup A\inΨ(G),\qquad S\cup B\inΨ(G),\qquad |T\cup A|=|S\cup B|. \] As a structural consequence, for every fixed $S\in \Psi (G)$ the map $T\mapsto S\cup T$ induces a canonical bijection from $\Psi (G-N[S])$ onto the members of $\Psi (G)$ containing $S$, and \[ α(G)=|S|+α(G-N[S]). \] This decomposition also yields explicit formulas for the intersection and the union of all the maximum independent sets extending $S$, together with counting formulas for the local maximum and maximum independent sets containing $S$. We also add a short visual guide to the framework $CritIndep(G)\subseteq Crown(G)\subseteq Psi(G)$ and end with several natural follow-up problems suggested by the theorem.

10 pages, 3 figures