Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.11418 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912962915074048 |
|---|---|
| author | Pereyra, Kevin |
| author_facet | Pereyra, Kevin |
| contents | A Kőnig--Egerváry graph is a graph $G$ satisfying
$α(G)+μ(G)=n(G)$, where $α(G)$, $μ(G)$, and $n(G)$ denote the
independence number, the matching number, and the order of $G$, respectively.
Let $\textnormal{core}(G)$ and $\textnormal{corona}(G)$ be the intersection
and the union of all maximum independent sets of $G$.
In this paper, we provide a complete characterization of graphs satisfying
$\a{\corona G}+\a{\core G}=2α(G)+1$,
thus giving a solution to an open problem posed by Levit and Mandrescu.
It is known that for a non-Kőnig--Egerváry graph with a unique odd cycle,
the following hold:
$\ker G=\textnormal{core}(G),\allowbreak\
\left|\textnormal{corona}(G)\right|
+\left|\textnormal{core}(G)\right|
=2α(G)+1,\allowbreak\
\textnormal{corona}(G)\cup N(\textnormal{core}(G))=V(G)$.
We extend these three results to a family of graphs containing an
arbitrarily large number of odd cycles. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11418 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A characterization of graphs with $\a{\corona G}+\a{\core G}=2α(G)+1$ Pereyra, Kevin Combinatorics A Kőnig--Egerváry graph is a graph $G$ satisfying $α(G)+μ(G)=n(G)$, where $α(G)$, $μ(G)$, and $n(G)$ denote the independence number, the matching number, and the order of $G$, respectively. Let $\textnormal{core}(G)$ and $\textnormal{corona}(G)$ be the intersection and the union of all maximum independent sets of $G$. In this paper, we provide a complete characterization of graphs satisfying $\a{\corona G}+\a{\core G}=2α(G)+1$, thus giving a solution to an open problem posed by Levit and Mandrescu. It is known that for a non-Kőnig--Egerváry graph with a unique odd cycle, the following hold: $\ker G=\textnormal{core}(G),\allowbreak\ \left|\textnormal{corona}(G)\right| +\left|\textnormal{core}(G)\right| =2α(G)+1,\allowbreak\ \textnormal{corona}(G)\cup N(\textnormal{core}(G))=V(G)$. We extend these three results to a family of graphs containing an arbitrarily large number of odd cycles. |
| title | A characterization of graphs with $\a{\corona G}+\a{\core G}=2α(G)+1$ |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.11418 |