Inequalities Involving Core, Corona, and Critical Sets in General Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918381912850432 |
|---|---|
| author | Pastine, Adrián Pereyra, Kevin |
| author_facet | Pastine, Adrián Pereyra, Kevin |
| contents | Let $α(G)$ denote the cardinality of a maximum independent set. An independent set $I$ of $G$ is critical if $\left|I\right|-\left|N(I)\right|\ge\left|J\right|-\left|N(J)\right|$ for every independent set $J$ of $G$. Let $\text{core}(G)$ and $\text{corona}(G)$ be the intersection/union of all maximum independent sets of $G$. Let $\text{ker}(G)$ and $\text{diadem}(G)$ be the intersection/union of all critical independent sets of $G$. In this paper we prove that \[ \left|\text{corona}(G)\right|+\left|\text{core}(G)\right|\le2α(G)+k, \] \noindent where $k$ is the number of vertex-distinct odd cycles in $G$, thus confirming a recent conjecture in the area. Moreover, we prove that \[ \left|\text{nucleus}(G)\right|+\left|\text{diadem}(G)\right|\le2α(G), \] \noindent thereby confirming another conjecture (Levit--Mandrescu 2014). As an application of these facts, we obtain a chain of inequalities \[ \left|\text{nucleus}(G)\right|+\left|\text{diadem}(G)\right|\le2α(G)\le\left|\text{corona}(G)\right|+\left|\text{core}(G)\right|\le2α(G)+k. \] \noindent The paper concludes with a collection of related open problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_10316 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Inequalities Involving Core, Corona, and Critical Sets in General Graphs Pastine, Adrián Pereyra, Kevin Combinatorics Let $α(G)$ denote the cardinality of a maximum independent set. An independent set $I$ of $G$ is critical if $\left|I\right|-\left|N(I)\right|\ge\left|J\right|-\left|N(J)\right|$ for every independent set $J$ of $G$. Let $\text{core}(G)$ and $\text{corona}(G)$ be the intersection/union of all maximum independent sets of $G$. Let $\text{ker}(G)$ and $\text{diadem}(G)$ be the intersection/union of all critical independent sets of $G$. In this paper we prove that \[ \left|\text{corona}(G)\right|+\left|\text{core}(G)\right|\le2α(G)+k, \] \noindent where $k$ is the number of vertex-distinct odd cycles in $G$, thus confirming a recent conjecture in the area. Moreover, we prove that \[ \left|\text{nucleus}(G)\right|+\left|\text{diadem}(G)\right|\le2α(G), \] \noindent thereby confirming another conjecture (Levit--Mandrescu 2014). As an application of these facts, we obtain a chain of inequalities \[ \left|\text{nucleus}(G)\right|+\left|\text{diadem}(G)\right|\le2α(G)\le\left|\text{corona}(G)\right|+\left|\text{core}(G)\right|\le2α(G)+k. \] \noindent The paper concludes with a collection of related open problems. |
| title | Inequalities Involving Core, Corona, and Critical Sets in General Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.10316 |