{
  "id": "math/0003057",
  "version": "v1",
  "published": "2000-03-09T19:55:18.000Z",
  "updated": "2000-03-09T19:55:18.000Z",
  "title": "On $α^{++}$-Stable Graphs",
  "authors": [
    "Vadim E. Levit",
    "Eugen Mandrescu"
  ],
  "comment": "11 pages, 3 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. A graph is well-covered if every maximal stable set has the same size. G is a Koenig-Egervary graph if its order equals alpha(G) + mu(G), where mu(G) is the cardinality of a maximum matching in G. In this paper we characterize $\\alpha ^{++}$-stable graphs, namely, the graphs whose stability numbers are invariant to adding any two edges from their complements. We show that a K\\\"{o}nig-Egerv\\'{a}ry graph is $\\alpha ^{++}$-stable if and only if it has a perfect matching consisting of pendant edges and no four vertices of the graph span a cycle. As a corollary it gives necessary and sufficient conditions for $\\alpha ^{++}$-stability of bipartite graphs and trees. For instance, we prove that a bipartite graph is $\\alpha ^{++}$-stable if and only if it is well-covered and C4-free.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2000-03-09T19:55:18.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C70",
      "05C05",
      "05C75"
    ],
    "keywords": [
      "stable graphs",
      "bipartite graph",
      "stability number",
      "order equals alpha",
      "maximal stable set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 11,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2000math......3057L"
    }
  }
}