On corona of Konig-Egervary graphs

Abstract

Let $\alpha (G)$ denote the cardinality of a maximum independent set and $\mu (G)$ be the size of a maximum matching of a graph $G=\left(V,E\right)$. If $\alpha (G)+\mu (G)=\left|V\right|$, then $G$ is a König-Egerváry graph, and $G$ is a $1$-König-Egerváry graph whenever $\alpha (G)+\mu (G)=\left|V\right|-1$. The corona $H\circ \mathcal{X}$ of a graph $H$ and a family of graphs $\mathcal{X}=\left\{X_i:1\le i\le \left|V(H)\right|\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|V(H)\right|$. In this paper we completely characterize graphs whose coronas are $k$-König-Egerváry graphs, where $k\in \left\{0,1\right\}$.

11 pages, 3 figures