Inequalities Involving Core, Corona, and Critical Sets in General Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _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 |