2016/04/18 by Michael A. Henning, Henning, Michael A., Anders Yeo +1
Computer Science · Mathematics · #05C70 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1604.05020
openalex publication_date 2016/04/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let k ≥ 3. We prove the following three bounds for the matching number, α'(G), of a graph, G, of order n size m and maximum degree at most k. If k is odd, then α'(G) ≥ ( (k-1)/(k(k2 - 3)) ) n + ( (k2 - k - 2)/(k(k2 - 3)) ) m - (k-1)/(k(k2 - 3)). If k is even, then α'(G) ≥ (n)/(k(k+1)) + (m)/(k+1) - (1)/(k). If k is even, then α'(G) ≥ ( (k+2)/(k2+k+2) ) m - ( (k-2)/(k2+k+2) ) n - (k+2)/(k2+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 Lk of pairs (γ,β) of real numbers with the following property. There exists a constant K such that α'(G) ≥ γn + β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 Lk is a convex set. Further, if k is odd, then Lk is the intersection of two closed half-spaces, and there is exactly one extreme point of Lk, while if k is even, then Lk is the intersection of three closed half-spaces, and there are precisely two extreme points of Lk.