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

Abstract

Given a graph $G$, the matching number of $G$, written ${\alpha }^{\prime }(G)$, is the maximum size of a matching in $G$, and the fractional matching number of $G$, written ${\alpha }_f^{\prime }(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_1$ nor $K_3$, then ${\alpha }_f^{\prime }(G)-{\alpha }^{\prime }(G)\le \frac{n-2}{6}$ and $\frac{{\alpha }_f^{\prime }(G)}{{\alpha }^{\prime }(G)}\le \frac{3n}{2n+2}$. Both inequalities are sharp, and we characterize the infinite family of graphs where equalities hold.

8 pages, 2 figures

Cited by in corpus (1)

• Fractional hypergraph isomorphism and fractional invariants