{
  "id": "math/0002070",
  "version": "v1",
  "published": "2000-02-10T13:28:02.000Z",
  "updated": "2000-02-10T13:28:02.000Z",
  "title": "On $α$-Critical Edges in König-Egerváry Graphs",
  "authors": [
    "Vadim E. Levit",
    "Eugen Mandrescu"
  ],
  "comment": "15 pages, 10 figures",
  "categories": [
    "math.CO"
  ],
  "abstract": "The stability number of a graph G, denoted by alpha(G), is the cardinality of a stable set of maximum size in G. If alpha(G-e) > alpha(G), then e is an alpha-critical edge, and if mu(G-e) < mu(G), then e is a mu-critical edge, where mu(G) is the cardinality of a maximum matching in G. G is a Koenig-Egervary graph if alpha(G) + mu(G) equals its order. Beineke, Harary and Plummer have shown that the set of alpha-critical edges of a bipartite graph is a matching. In this paper we generalize this statement to Koenig-Egervary graphs. We also prove that in a Koenig-Egervary graph alpha-critical edges are also mu-critical, and that they coincide in bipartite graphs. We obtain that for any tree its stability number equals the sum of the cardinality of the set of its alpha-critical vertices and the size of the set of its alpha-critical edges. Eventually, we characterize the Koenig-Egervary graphs enjoying this property.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2000-02-10T13:28:02.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C70",
      "05C05",
      "05C75"
    ],
    "keywords": [
      "könig-egerváry graphs",
      "bipartite graph",
      "stability number equals",
      "cardinality",
      "koenig-egervary graph alpha-critical edges"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 15,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math......2070L"
    }
  }
}