{
  "id": "1202.0681",
  "version": "v2",
  "published": "2012-02-03T12:39:14.000Z",
  "updated": "2012-08-10T14:34:39.000Z",
  "title": "On maximum matchings in almost regular graphs",
  "authors": [
    "Petros A. Petrosyan"
  ],
  "comment": "5 pages",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "In 2010, Mkrtchyan, Petrosyan and Vardanyan proved that every graph $G$ with $2\\leq \\delta(G)\\leq \\Delta(G)\\leq 3$ contains a maximum matching whose unsaturated vertices do not have a common neighbor, where $\\Delta(G)$ and $\\delta(G)$ denote the maximum and minimum degrees of vertices in $G$, respectively. In the same paper they suggested the following conjecture: every graph $G$ with $\\Delta(G)-\\delta(G)\\leq 1$ contains a maximum matching whose unsaturated vertices do not have a common neighbor. Recently, Picouleau disproved this conjecture by constructing a bipartite counterexample $G$ with $\\Delta(G)=5$ and $\\delta(G)=4$. In this note we show that the conjecture is false for graphs $G$ with $\\Delta(G)-\\delta(G)=1$ and $\\Delta(G)\\geq 4$, and for $r$-regular graphs when $r\\geq 7$.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-08-10T14:34:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "regular graphs",
      "maximum matching",
      "common neighbor",
      "unsaturated vertices",
      "conjecture"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1202.0681P"
    }
  }
}