The difference and ratio of the fractional matching number and the matching number of graphs

Original · EN

Given a graph G, the matching number of G, written α'(G), is the maximum size of a matching in G, and the fractional matching number of G, written α'f(G), is the maximum size of a fractional matching of G. In this paper, we prove that if G is an n-vertex connected graph that is neither K₁ nor K₃, then α'f(G)-α'(G) ≤ n-26 and α'f(G)/α'(G) ≤ 3n/2n+2. Both inequalities are sharp, and we characterize the infinite family of graphs where equalities hold.