{
  "id": "1501.07549",
  "version": "v1",
  "published": "2015-01-29T19:14:39.000Z",
  "updated": "2015-01-29T19:14:39.000Z",
  "title": "Equimatchable factor-critical graphs and independence number 2",
  "authors": [
    "Eduard Eiben",
    "Michal Kotrbcik"
  ],
  "comment": "14 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "A graph is equimatchable if each of its matchings is a subset of a maximum matching. It is known that any 2-connected equimatchable graph is either bipartite, or factor-critical, and that these two classes are disjoint. This paper provides a description of k-connected equimatchable factor-critical graphs with respect to their k-cuts for $k\\ge 3$. As our main result we prove that if G is a k-connected equimatchable factor-critical graph with at least 2k+3 vertices and a k-cut S, then G-S has exactly two components and both these components are close to being complete or complete bipartite. If both components of G-S additionally have at least 3 vertices and $k\\ge 4$, then the graph has independence number 2. On the other hand, since every 2-connected odd graph with independence number 2 is equimatchable, we get the following result. For any $k\\ge 4$ let G be a k-connected odd graph with at least 2k+3 vertices and a k-cut S such that G-S has two components with at least 3 vertices. Then G has independence number 2 if and only if it is equimatchable and factor-critical. Furthermore, we show that a 2-connected odd graph G with at least 4 vertices has independence number at most 2 if and only if G is equimatchable and factor-critical and G+e is equimatchable for every edge of the complement of G.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-01-29T19:14:39.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70"
    ],
    "keywords": [
      "independence number",
      "k-connected equimatchable factor-critical graph",
      "components",
      "main result",
      "complete bipartite"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150107549E"
    }
  }
}