New results relating independence and matchings

Abstract

In this paper we study relationships between the \emph{matching number}, written $\hat{I}¼(G)$, and the \emph{independence number}, written $\hat{I}\pm (G)$. Our first main result is to show \[ α(G) \le μ(G) + |X| - μ(G[N_G[X]]), \] where $X$ is \emph{any} intersection of maximum independent sets in $G$. Our second main result is to show \[ δ(G)α(G) \le Δ(G)μ(G), \] where $\hat{I}´(G)$ and $\hat{I}”(G)$ denote the minimum and maximum vertex degrees of $G$, respectively. These results improve on and generalize known relations between $\hat{I}¼(G)$ and $\hat{I}\pm (G)$. Further, we also give examples showing these improvements.