Temat: matching number - Katalog OPAC zbiorów

Skocz do pozycji: 1.

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[N_G[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ł

Skocz do pozycji: 2.

Tytuł:: On the Independence Number of Traceable 2-Connected Claw-Free Graphs
Autorzy:: Wang, Shipeng
Xiong, Liming
Powiązania:: https://bibliotekanauki.pl/articles/31343185.pdf
Data publikacji:: 2019-11-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: traceability
independence number
matching number
trail
closure
Opis:: A well-known theorem by Chvátal-Erdőos [A note on Hamilton circuits, Discrete Math. 2 (1972) 111–135] states that if the independence number of a graph G is at most its connectivity plus one, then G is traceable. In this article, we show that every 2-connected claw-free graph with independence number α(G) ≤ 6 is traceable or belongs to two exceptional families of well-defined graphs. As a corollary, we also show that every 2-connected claw-free graph with independence number α(G) ≤ 5 is traceable.
Źródło:: Discussiones Mathematicae Graph Theory; 2019, 39, 4; 925-937
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 3.

Tytuł:: On a special case of Hadwigers conjecture
Autorzy:: Plummer, Michael
Stiebitz, Michael
Toft, Bjarne
Powiązania:: https://bibliotekanauki.pl/articles/743179.pdf
Data publikacji:: 2003
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: Hadwiger's Conjecture
complete minor
independence number
connected matching
Opis:: Hadwiger's Conjecture seems difficult to attack, even in the very special case of graphs G of independence number α(G) = 2. We present some results in this special case.
Źródło:: Discussiones Mathematicae Graph Theory; 2003, 23, 2; 333-363
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 4.

Tytuł:: A note of arbitrarily vertex decomposable graphs
Autorzy:: Marczyk, A.
Powiązania:: https://bibliotekanauki.pl/articles/254919.pdf
Data publikacji:: 2006
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: arbitrarily vertex decomposable graphs
traceable graphs
independence number
perfect matching
Opis:: A graph G of order n is said to be arbitrarily vertex decomposable if for each sequence (n1,..., nk) of positive integers such that n1 + ... + nk = n there exists a partition (V1,..., Vk) of the vertex set of G such that for each i ∈ {1,..., k}, Vi induces a connected subgraph of G on ni vertices. In this paper we show that if G is a two-connected graph on n vertices with the independence number at most ⌈n/2⌉ and such that the degree sum of any pair of non-adjacent vertices is at least n - 3, then G is arbitrarily vertex decomposable. We present another result for connected graphs satisfying a similar condition, where the bound n - 3 is replaced by n - 2.
Źródło:: Opuscula Mathematica; 2006, 26, 1; 109-118
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja