Core and Corona in 2-Bicritical Odd-Bicyclic Graphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915856426991616 |
|---|---|
| author | Pereyra, Kevin |
| author_facet | Pereyra, Kevin |
| contents | Let $\core G$ and $\corona G$ denote the intersection and the union, respectively, of all maximum independent sets of a graph $G$. A graph is called \emph{$2$-bicritical} if $\a{N(S)}>\a S$ for every nonempty independent set $S$. Pulleyblank 1979 showed that almost all graphs are $2$-bicritical.
In this paper, we study the structure of maximum independent sets in $2$-bicritical graphs with at most two odd cycles. Using ear--pendant decompositions, we obtain a complete structural classification of these graphs into four families: one-odd cycle, fused-odd, even-linked, and odd-linked graphs. For each family, we compute explicitly $α(G)$, $\core G$, and $\corona G$, and describe the corresponding matching structure.
We prove that $\a{\core G}+\a{\corona G}$ equals either $2α(G),2α(G)+1$ or $2α(G)+2$, and we give a complete, purely structural characterization of the graphs in each case in terms of the relative position of their odd cycles.
These results extend a theory originally developed for
König--Egerváry graphs and later for almost bipartite graphs
to a broader non-König--Egerváry setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11419 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Core and Corona in 2-Bicritical Odd-Bicyclic Graphs Pereyra, Kevin Combinatorics Let $\core G$ and $\corona G$ denote the intersection and the union, respectively, of all maximum independent sets of a graph $G$. A graph is called \emph{$2$-bicritical} if $\a{N(S)}>\a S$ for every nonempty independent set $S$. Pulleyblank 1979 showed that almost all graphs are $2$-bicritical. In this paper, we study the structure of maximum independent sets in $2$-bicritical graphs with at most two odd cycles. Using ear--pendant decompositions, we obtain a complete structural classification of these graphs into four families: one-odd cycle, fused-odd, even-linked, and odd-linked graphs. For each family, we compute explicitly $α(G)$, $\core G$, and $\corona G$, and describe the corresponding matching structure. We prove that $\a{\core G}+\a{\corona G}$ equals either $2α(G),2α(G)+1$ or $2α(G)+2$, and we give a complete, purely structural characterization of the graphs in each case in terms of the relative position of their odd cycles. These results extend a theory originally developed for König--Egerváry graphs and later for almost bipartite graphs to a broader non-König--Egerváry setting. |
| title | Core and Corona in 2-Bicritical Odd-Bicyclic Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.11419 |