A 2-dominating set of a graph G is a set D of vertices of G such that every vertex not in D has a at least two neighbors in D. The 2-domination number of a graph G, denoted by gamma_2(G), is the minimum cardinality of a 2-dominating set of G. Fink and Jacobson [n-domination in graphs, Graph theory with applications to algorithms and computer science, Wiley, New York, 1985, 283-300] established the following lower bound on the 2-domination number of a tree in term of its order, gamma_2(T) >= (n+1)/2. We give an alternative proof of this bound.
Autorzy
Informacje dodatkowe
- Kategoria
- Publikacja w czasopiśmie
- Typ
- artykuły w czasopismach
- Język
- angielski
- Rok wydania
- 2010
Źródło danych: MOSTWiedzy.pl - publikacja "An Alternative Proof of a Lower Bound on the 2-Domination Number of a Tree" link otwiera się w nowej karcie
