Temat: independence number - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: Trees with equal 2-domination and 2-independence numbers
Autorzy:: Chellali, Mustapha
Meddah, Nacéra
Powiązania:: https://bibliotekanauki.pl/articles/743338.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: 2-domination number
2-independence number
trees
Opis:: Let G = (V,E) be a graph. A subset S of V is a 2-dominating set if every vertex of V-S is dominated at least 2 times, and S is a 2-independent set of G if every vertex of S has at most one neighbor in S. The minimum cardinality of a 2-dominating set a of G is the 2-domination number γ₂(G) and the maximum cardinality of a 2-independent set of G is the 2-independence number β₂(G). Fink and Jacobson proved that γ₂(G) ≤ β₂(G) for every graph G. In this paper we provide a constructive characterization of trees with equal 2-domination and 2-independence numbers.
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 2; 263-270
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Skocz do pozycji: 2.

Tytuł:: Bounds on the 2-domination number in cactus graphs
Autorzy:: Chellali, M.
Powiązania:: https://bibliotekanauki.pl/articles/254915.pdf
Data publikacji:: 2006
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: 2-domination number
total domination number
independence number
cactus graphs
trees
Opis:: A 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in S is dominated at least twice. The minimum cardinality of a 2-dominating set of G is the 2-domination number γ2(G). We show that if G is a nontrivial connected cactus graph with k(G) even cycles (k(G) ≥ 0), then γ2(G) ≥ γt(G) - k(G), and if G is a graph of order n with at most one cycle, then γ2(G) ≥ (n + l - s)/2 improving Fink and Jacobson's lower bound for trees with l > s, where γt(G), l and s are the total domination number, the number of leaves and support vertices of G, respectively. We also show that if T is a tree of order n ≥ 3, then γ2(T) ≤ β(T) + s - 1, where β(T) is the independence number of T.
Źródło:: Opuscula Mathematica; 2006, 26, 1; 5-12
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Informacja