{
  "id": "1604.05020",
  "version": "v1",
  "published": "2016-04-18T07:37:27.000Z",
  "updated": "2016-04-18T07:37:27.000Z",
  "title": "Tight lower bounds on the matching number in a graph with given maximum degree",
  "authors": [
    "Michael A. Henning",
    "Anders Yeo"
  ],
  "comment": "40 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Let $k \\geq 3$. We prove the following three bounds for the matching number, $\\alpha'(G)$, of a graph, $G$, of order $n$ size $m$ and maximum degree at most $k$. If $k$ is odd, then $\\alpha'(G) \\ge \\left( \\frac{k-1}{k(k^2 - 3)} \\right) n \\, + \\, \\left( \\frac{k^2 - k - 2}{k(k^2 - 3)} \\right) m \\, - \\, \\frac{k-1}{k(k^2 - 3)}$. If $k$ is even, then $\\alpha'(G) \\ge \\frac{n}{k(k+1)} \\, + \\, \\frac{m}{k+1} - \\frac{1}{k}$. If $k$ is even, then $\\alpha'(G) \\ge \\left( \\frac{k+2}{k^2+k+2} \\right) m \\, - \\, \\left( \\frac{k-2}{k^2+k+2} \\right) n \\, - \\frac{k+2}{k^2+k+2}$. In this paper we actually prove a slight strengthening of the above for which the bounds are tight for essentially all densities of graphs. The above three bounds are in fact powerful enough to give a complete description of the set $L_k$ of pairs $(\\gamma,\\beta)$ of real numbers with the following property. There exists a constant $K$ such that $\\alpha'(G) \\geq \\gamma n + \\beta m - K$ for every connected graph $G$ with maximum degree at most~$k$, where $n$ and $m$ denote the number of vertices and the number of edges, respectively, in $G$. We show that $L_k$ is a convex set. Further, if $k$ is odd, then $L_k$ is the intersection of two closed half-spaces, and there is exactly one extreme point of $L_k$, while if $k$ is even, then $L_k$ is the intersection of three closed half-spaces, and there are precisely two extreme points of $L_k$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-04-18T07:37:27.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C70"
    ],
    "keywords": [
      "maximum degree",
      "tight lower bounds",
      "matching number",
      "extreme point",
      "closed half-spaces"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 40,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160405020H"
    }
  }
}