pith. sign in

arxiv: 1512.07595 · v1 · pith:G5L52SSTnew · submitted 2015-12-23 · 🧮 math.CO

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

classification 🧮 math.CO
keywords alphamatchingnumberfracfractionalgraphgraphsmaximum
0
0 comments X
read the original abstract

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

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.