Geodesic
New Results Relating Independence and Matchings
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 921-935

Voir la notice de l'article provenant de la source Library of Science

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.
Keywords: independent sets, independence number, matchings, matching number 
@article{DMGT_2022_42_3_a14,
     author = {Caro, Yair and Davila, Randy and Pepper, Ryan},
     title = {New {Results} {Relating} {Independence} and {Matchings}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {921--935},
     publisher = {mathdoc},
     volume = {42},
     number = {3},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/}
}
TY  - JOUR
AU  - Caro, Yair
AU  - Davila, Randy
AU  - Pepper, Ryan
TI  - New Results Relating Independence and Matchings
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 921
EP  - 935
VL  - 42
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/
LA  - en
ID  - DMGT_2022_42_3_a14
ER  - 
%0 Journal Article
%A Caro, Yair
%A Davila, Randy
%A Pepper, Ryan
%T New Results Relating Independence and Matchings
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 921-935
%V 42
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/
%G en
%F DMGT_2022_42_3_a14
Caro, Yair; Davila, Randy; Pepper, Ryan. New Results Relating Independence and Matchings. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 3, pp. 921-935. http://geodesic.mathdoc.fr/item/DMGT_2022_42_3_a14/