























In this paper we study relationships between the \emph{matching number}, written $μ(G)$, and the \emph{independence number}, written $α(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 $δ(G)$ and $Δ(G)$ denote the minimum and maximum vertex degrees of $G$, respectively. These results improve on and generalize known relations between $μ(G)$ and $α(G)$. Further, we also give examples showing these improvements.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。