{
  "id": "2411.12863",
  "version": "v1",
  "published": "2024-11-19T21:12:07.000Z",
  "updated": "2024-11-19T21:12:07.000Z",
  "title": "On corona of Konig-Egervary graphs",
  "authors": [
    "Vadim E. Levit",
    "Eugen Mandrescu"
  ],
  "comment": "11 pages, 3 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "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\\vert V\\right\\vert $, then $G$ is a K\\\"{o}nig-Egerv\\'{a}ry graph, and $G$ is a $1$-K\\\"{o}nig-Egerv\\'{a}ry graph whenever $\\alpha(G)+\\mu(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\\\"{o}nig-Egerv\\'{a}ry graphs, where $k\\in\\left\\{ 0,1\\right\\} $.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-11-19T21:12:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C70",
      "G.2.2"
    ],
    "keywords": [
      "konig-egervary graphs",
      "maximum independent set",
      "cardinality",
      "characterize graphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}