The family of all local maximum independent sets is an augmentoid
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917359280717824 |
|---|---|
| author | Levit, Vadim E. Mandrescu, Eugen |
| author_facet | Levit, Vadim E. Mandrescu, Eugen |
| contents | 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 $Ψ(G)$ of local maximum independent sets, and asked in Problem~5.5 to characterize the graphs whose family $Ψ(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),Ψ(G))$ is an augmentoid. The proof is constructive. If $S,T\inΨ(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Ψ(G)$ the map $T\mapsto S\cup T$ induces a canonical bijection from $Ψ(G-N[S])$ onto the members of $Ψ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_22688 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The family of all local maximum independent sets is an augmentoid Levit, Vadim E. Mandrescu, Eugen Combinatorics Discrete Mathematics Primary 05C69, Secondary 05B35, 05C70 G.2.2 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 $Ψ(G)$ of local maximum independent sets, and asked in Problem~5.5 to characterize the graphs whose family $Ψ(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),Ψ(G))$ is an augmentoid. The proof is constructive. If $S,T\inΨ(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Ψ(G)$ the map $T\mapsto S\cup T$ induces a canonical bijection from $Ψ(G-N[S])$ onto the members of $Ψ(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. |
| title | The family of all local maximum independent sets is an augmentoid |
| topic | Combinatorics Discrete Mathematics Primary 05C69, Secondary 05B35, 05C70 G.2.2 |
| url | https://arxiv.org/abs/2603.22688 |