2019/09/19 by Caro, Yair, Davila, Randy, Pepper, Ryan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1909.09093
In this paper we study relationships between the matching number, written μ(G), and the independence number, written α(G). Our first main result is to show α(G) ≤ μ(G) + |X| - μ(G[NG[X]]), where X is any intersection of maximum independent sets in G. Our second main result is to show δ(G)α(G) ≤ Δ(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.