- Tytuł:
- New Results Relating Independence and Matchings
- Autorzy:
-
Caro, Yair
Davila, Randy
Pepper, Ryan - Powiązania:
- https://bibliotekanauki.pl/articles/32304143.pdf
- Data publikacji:
- 2022-08-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
independent sets
independence number
matchings
matching number - Opis:
- 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.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2022, 42, 3; 921-935
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł