Narzędzia help

Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
first last
cannonical link button


Opuscula Mathematica

Tytuł artykułu

Bounds on the 2-domination number in cactus graphs

Autorzy Chellali, M. 
Treść / Zawartość
Warianty tytułu
Języki publikacji EN
EN 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.
Słowa kluczowe
EN 2-domination number   total domination number   independence number   cactus graphs   trees  
Wydawca AGH University of Science and Technology Press
Czasopismo Opuscula Mathematica
Rocznik 2006
Tom Vol. 26, no. 1
Strony 5--12
Opis fizyczny Bibliogr. 9 poz., rys.
autor Chellali, M.
[1] Blidia M., Chellali M., Favaron O., Independence and 2-domination in trees. Australasian J. Comb. 33 (2005), 317-327.
[2] Blidia M., Chellali M., Volkmann L., Bounds of the 2-domination number of graphs Utilitas Math., to appear.
[3] Favaron O., On a conjecture of Fink and Jacobson concerning k-domination and k-dependence. J. Combinat. Theory Ser. B 39 (1985), 101-102.
[4] Favaron O. A bound on the independent domination number of a tree, Int. J. Graph Theory 1(1) (1992), 19-27.
[5] Fink J. F., Jacobson M. S., n-domination in graphs, in: Alavi Y. and Schwenk A. J. (eds), Graph Theory with Applications to Algorithms and Computer Science, New York, Wiley, 1985, 283-300.
[6] Fink J.F., Jacobson M. S., On n-domination, n-dependence and forbidden sub-graphs. Graph Theory with Applications to Algorithms and Computer Science. New York, Wiley, 1985, 301-312.
[7] Haynes T. W., Hedetniemi S. T., Henning M.A., Slater P. J., H-forming sets in graphs, Discrete Mathematics 262 (2003), 159-169.
[8] Haynes T. W., Hedetniemi S.T., Slater P. J., Fundamentals of Domination in Graphs, Marcel Dekker, New York, 1998.
[9] Haynes T.W., Hedetniemi S.T., Slater P.J. (eds), Domination in Graphs: Advanced Topics, Marcel Dekker, New York, 1998.
Kolekcja BazTech
Identyfikator YADDA bwmeta1.element.baztech-article-AGH4-0006-0001