On corona of Konig-Egervary graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910705571069952 |
|---|---|
| author | Levit, Vadim E. Mandrescu, Eugen |
| author_facet | Levit, Vadim E. Mandrescu, Eugen |
| contents | Let $α(G)$ denote the cardinality of a maximum independent set and $μ(G)$ be the size of a maximum matching of a graph $G=\left( V,E\right) $. If $α(G)+μ(G)=\left\vert V\right\vert $, then $G$ is a König-Egerváry graph, and $G$ is a $1$-König-Egerváry graph whenever $α(G)+μ(G)=\left\vert V\right\vert -1$. The corona $H\circ\mathcal{X}$ of a graph $H$ and a family of graphs $\mathcal{X}=\left\{ X_{i}:1\leq i\leq\left\vert V(H)\right\vert \right\} $ is obtained by joining each vertex $v_{i}$ of $H$ to all the vertices of the corresponding graph $X_{i},i=1,2,...,\left\vert V(H)\right\vert $.
In this paper we completely characterize graphs whose coronas are $k$-König-Egerváry graphs, where $k\in\left\{ 0,1\right\} $. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_12863 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On corona of Konig-Egervary graphs Levit, Vadim E. Mandrescu, Eugen Combinatorics Discrete Mathematics 05C69 (Primary) 05C70 (Secondary) G.2.2 Let $α(G)$ denote the cardinality of a maximum independent set and $μ(G)$ be the size of a maximum matching of a graph $G=\left( V,E\right) $. If $α(G)+μ(G)=\left\vert V\right\vert $, then $G$ is a König-Egerváry graph, and $G$ is a $1$-König-Egerváry graph whenever $α(G)+μ(G)=\left\vert V\right\vert -1$. The corona $H\circ\mathcal{X}$ of a graph $H$ and a family of graphs $\mathcal{X}=\left\{ X_{i}:1\leq i\leq\left\vert V(H)\right\vert \right\} $ is obtained by joining each vertex $v_{i}$ of $H$ to all the vertices of the corresponding graph $X_{i},i=1,2,...,\left\vert V(H)\right\vert $. In this paper we completely characterize graphs whose coronas are $k$-König-Egerváry graphs, where $k\in\left\{ 0,1\right\} $. |
| title | On corona of Konig-Egervary graphs |
| topic | Combinatorics Discrete Mathematics 05C69 (Primary) 05C70 (Secondary) G.2.2 |
| url | https://arxiv.org/abs/2411.12863 |