{
  "id": "2103.11550",
  "version": "v1",
  "published": "2021-03-22T02:51:22.000Z",
  "updated": "2021-03-22T02:51:22.000Z",
  "title": "A tight lower bound on matching number of graphs",
  "authors": [
    "Xiaofeng Gu",
    "Muhuo Liu"
  ],
  "comment": "The manuscript was originally done in May 2020",
  "categories": [
    "math.CO"
  ],
  "abstract": "The matching number of a graph $G$, denoted by $\\alpha'(G)$, is the size of a maximum matching in $G$. The matching number of regular graphs has been well studied, however, not as much is known for general graphs. Haxell and Scott gave a complete description for the lower bound on the matching number of a graph with maximum degree at most 3 in terms of the number of vertices with fixed degree. Similar idea was used by Henning and Yeo, who established a tight lower bound on the matching number of a graph with given maximum degree in terms of the numbers of vertices and edges. We discover a tight lower bound on the matching number of general graphs via eigenvalues of combinatorial Laplacian. Let $\\mu_i$ denotes the $i$th smallest eigenvalue of the Laplacian matrix of a graph. In this paper, we show that $\\alpha'(G)\\ge \\min\\{\\frac{\\mu_2}{\\mu_n}(n -1), \\frac{1}{2}(n-1)\\}$ for a nonempty graph $G$ on $n$ vertices, strengthening a theorem of Brouwer and Haemers who showed that if $2\\mu_2 \\ge \\mu_n$, then $G$ has a perfect matching. Moreover, the lower bound is tight. We contribute a useful lemma in the proof, which is of its own interest, and as applications, we prove similar results for factor-critical graphs, the number of balloons, spanning even subgraphs, as well as spanning trees with bounded degree.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-03-22T02:51:22.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "tight lower bound",
      "matching number",
      "maximum degree",
      "general graphs",
      "th smallest eigenvalue"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}